蓝桥杯2015c++A组真题&代码第十题灾后重建
蓝桥杯2015c++A组真题&代码第十题灾后重建
下面结合 kruskal 最小生成树算法 + 倍增法求解
关于倍增法可以参考:
https://blog.****.net/lw277232240/article/details/72870644
/*
灾后重建
Pear市一共有N(<=50000)个居民点,居民点之间有M(<=200000)条双向道路相连。这些居民点两两之间都可以通过双向道路到达。
这种情况一直持续到最近,一次严重的地震毁坏了全部M条道路。
震后,Pear打算修复其中一些道路,修理第i条道路需要Pi的时间。不过,Pear并不打算让全部的点连通,而是选择一些标号特殊的点让他们连通。
Pear有Q(<=50000)次询问,每次询问,他会选择所有编号在[tl,tr]之间,并且 编号 mod K = C 的点,修理一些路使得它们连通。
由于所有道路的修理可以同时开工,所以完成修理的时间取决于花费时间最长的一条路,即涉及到的道路中Pi的最大值。
你能帮助Pear计算出每次询问时需要花费的最少时间么?这里询问是独立的,也就是上一个询问里的修理计划并没有付诸行动。
【输入格式】
第一行三个正整数N、M、Q,含义如题面所述。
接下来M行,每行三个正整数Xi、Yi、Pi,表示一条连接Xi和Yi的双向道路,修复需要Pi的时间。可能有自环,可能有重边。1<=Pi<=1000000。
接下来Q行,每行四个正整数Li、Ri、Ki、Ci,表示这次询问的点是[Li,Ri]区间中所有编号Mod Ki=Ci的点。保证参与询问的点至少有两个。
【输出格式】
输出Q行,每行一个正整数表示对应询问的答案。
【样例输入】
7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9
1 7 1 0
1 7 3 1
2 5 1 0
3 7 2 1
【样例输出】
9
6
8
8
【数据范围】
对于20%的数据,N,M,Q<=30
对于40%的数据,N,M,Q<=2000
对于100%的数据,N<=50000,M<=2*10^5,Q<=50000. Pi<=10^6. Li,Ri,Ki均在[1,N]范围内,Ci在[0,对应询问的Ki)范围内。
资源约定:
峰值内存消耗 < 256M
CPU消耗 < 5000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准,不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>, 不能通过工程设置而省略常用头文件。
提交时,注意选择所期望的编译器类型。
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int N, M, Q;
const int MaxM = 2e5;//修正4:不能用10^5
const int MaxN = 50001;
/*边的抽象*/
struct Edge {
int from, to, cost;//起点,终点,代价
Edge(int from, int to, int cost) {
this->from = from;
this->to = to;
this->cost = cost;
}
};
bool cmp(Edge *e1, Edge *e2) {
return e1->cost < e2->cost;
}
Edge *edges[MaxM];
/*并查集*/
struct UFNode {
UFNode *parent;
UFNode() : parent(NULL) {}
};
UFNode *find(UFNode *p) {
if (p->parent == NULL)return p;
set<UFNode *> path;
while (p->parent != NULL) {
path.insert(p);
p = p->parent;
}
set<UFNode *>::iterator iter = path.begin();
while (iter != path.end()) {
(*iter)->parent = p;
iter++;//修正1.指针后移
}
return p;
}
void merge(UFNode *p1, UFNode *p2) {
find(p2)->parent = find(p1);
}
UFNode ufnodes[MaxN];//并查集的节点,一开始各自独立
/*最小树的生成及表示*/
vector<Edge *> mst[MaxN];
void buildMST() {
int cnt = 0;//已加入边的数量
for (int i = 0; i < M; ++i) {
Edge *pEdge = edges[i];
int from = pEdge->from;
int to = pEdge->to;
int cost = pEdge->cost;
if (find(&ufnodes[from]) == find(&ufnodes[to]))//这两个点已经在一棵树上,这条边不能采纳
continue;
else {
merge(&ufnodes[from], &ufnodes[to]);
cnt++;
// 将边加入到mst(邻接表)
mst[from].push_back(pEdge);
Edge *other = new Edge(to, from, cost);
mst[to].push_back(other);
if (cnt == N - 1)//构建完成
{
break;
}
}
}
}
int ff[MaxN][17];//ff[i][j]指的是标号为i的节点往根节点的方向移动2^i次达到的节点的标号 ff[i][j]=ff[ff[i][j-1]][j-1]
int mm[MaxN][17];//mm[i][j]指的是标号为i的节点往根节点的方向移动2^i次过程中的最大权
int depth[MaxN];//记录每个点在mst中的深度
int vis[MaxN];//记录某个点是否被访问过
/**
*
* @param start 开始的点标号
* @param parent 父节点标号
* @param depth 这个点的深度
*/
void dfs(int start, int parent, int d) {
depth[start] = d + 1;
vis[start] = 1;
// 先向上走
for (int i = 1; i < 17; ++i) {
ff[start][i] = ff[ff[start][i - 1]][i - 1];
mm[start][i] = max(mm[start][i - 1], mm[ff[start][i - 1]][i - 1]);
}
// 向下递归,找到所有儿子(所有邻居)
for (int i = 0; i < mst[start].size(); ++i) {
Edge *child = mst[start][i];//儿子
if (vis[child->to])continue;
ff[child->to][0] = start;
mm[child->to][0] = child->cost;
dfs(child->to, start, d + 1);
}
}
void preLca() {
ff[1][0] = 1;//定义1号节点为根节点
mm[1][0] = 0;//定义1号节点为根节点,它向上一步就没了,
dfs(1, 1, 0);
}
/*倍增法,求lca,顺便求max权重*/
int maxUsingLca(int a, int b) {
int ans = -1;
// 1.将a深度调到更深(交换)
if (depth[a] < depth[b]) {
int t = a;
a = b;
b = t;
}
//2.将a调到和b同一高度
int k = depth[a] - depth[b];//高度差
for (int i = 0; (1 << i) <= k; ++i) {//k的二进制101
if ((1 << i) & k)//k二进制的第i(从右往左)位是1
{
ans = max(ans, mm[a][i]);
a = ff[a][i];
}
}
// 至此,a和b已经在同一层上
//从最顶层开始遍历,求ab两点的lca的下一层
if(a!=b) {//重要更新
for (int j = 16; j >= 0; --j) {
if (ff[a][j] == ff[b][j])continue;
//从最大祖先开始,判断a,b祖先,是否相同,
// 一开始肯定相同,直到它们都跳j到最近祖先的下一层时,这个else触发
else {
ans = max(ans, mm[a][j]);
ans = max(ans, mm[b][j]);
a = ff[a][j];
b = ff[b][j];
// break;//重要更新
}
}
// 至此,a,b离lca还差一步
//再往上走一步就得到了lca
ans = max(ans, mm[a][0]);
ans = max(ans, mm[b][0]);
}
return ans;
}
void mid(int l, int r, int mod, int c) {
int ans = -1;
int left = l - l % mod + c;
if (left < l)left += mod;
// 遍历关注点,两两在mst中用倍增法求lca顺便求max权重
for (; left + mod <= r; left += mod) {
ans = max(ans, maxUsingLca(left, left + mod));
}
printf("%d\n", ans);
}
int main(int argc, const char *argv[]) {
// freopen("/Users/zhengwei/CLionProjects/lanqiao2018/2015_c_a/in/in5.txt", "r", stdin);
scanf("%d %d %d", &N, &M, &Q);
for (int i = 0; i < M; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
Edge *e = new Edge(a, b, c);
edges[i] = e;
}
// 排序
sort(edges, edges + M, cmp);//修正3.排序边界
buildMST();//生成最小树
preLca();//在最小树为倍增法做预处理
for (int i = 0; i < Q; ++i) {
int l, r, mod, c;
scanf("%d %d %d %d", &l, &r, &mod, &c);
mid(l, r, mod, c);
}
return 0;
}
#本人的写法,重新写了一遍
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 50005;
int N,M,Q;
int father[MAXN];
int level[MAXN];
int depth[MAXN];
int ff[MAXN][17];
int mm[MAXN][17];
struct edge{
int from,to,cost;
edge(int from,int to,int cost): from(from),to(to),cost(cost){};
};
struct node{
int to,cost,rec;
node(int to,int cost,int rec):to(to),cost(cost),rec(rec){};
};
vector<edge> arr;
vector<node> map[MAXN];
void add_edge(int from,int to,int cost){
map[from].push_back(node(to,cost,map[to].size()));
map[to].push_back(node(from,cost,map[from].size()-1));
}
bool cmp(const edge &a,const edge &b){
return a.cost<b.cost;
}
void init(){
for(int i=1;i<=N;i++){
father[i] = i;
level[i]= 1;
}
}
int find(int u){
if(father[u]!=u){
father[u] = find(father[u]);
}
return father[u];
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x==y) return;
if(level[x]>level[y]){
father[y] = x;
}else{
father[x] = y;
if(level[x]==level[y]){
level[y]++;
}
}
}
bool same(int x,int y){
return find(x)==find(y);
}
void buildMST(){
sort(arr.begin(),arr.end(),cmp);
// for(int i=0;i<arr.size();i++){
// printf("%d %d %d \n",arr[i].from,arr[i].to,arr[i].cost);
// }
init();
for(int i=1,j=0;i<=N-1 && j<arr.size();j++){
edge e = arr[j];
if(same(e.from,e.to)) continue;
unite(e.from,e.to);
add_edge(e.from,e.to,e.cost);
i++;
}
}
void dfs(int start,int parent,int d){
depth[start] = d;
for(int i=1;i<=16;i++){
ff[start][i] = ff[ff[start][i-1]][i-1];
mm[start][i] = max(mm[start][i-1],mm[ff[start][i-1]][i-1]);
}
for(int i=0;i<map[start].size();i++){
node nn = map[start][i];
if(nn.to == parent) continue;
ff[nn.to][0] = start;
mm[nn.to][0] = nn.cost;
dfs(nn.to,start,d+1);
}
}
int usingLca(int a,int b){
if(depth[a]<depth[b]){
swap(a,b);
}
int k = depth[a] - depth[b];
int ans = -1;
for(int i=0;(1<<i)<=k;i++){
if((k>>i)&1){
ans = max(ans,mm[a][i]);
a = ff[a][i];
}
}
for(int i=16;i>=0;i--){
if(ff[a][i] == ff[b][i])continue;
ans = max(ans,mm[a][i]);
ans = max(ans,mm[b][i]);
a = ff[a][i];
b = ff[b][i];
}
ans = max(ans,mm[a][0]);
ans = max(ans,mm[b][0]);
return ans;
}
void buildLca(){
ff[1][0] = 1;
mm[1][0] = 0;
dfs(1,-1,1);
}
int mid(int left,int right,int mod,int c){
int l = left-left%mod +c;
if(l<left) l+=mod;
int ans = -1;
for(int i=l;i+mod<=right;i+=mod){
ans = max(ans,usingLca(i,i+mod));
}
return ans;
}
int Inquery(){
buildMST();
buildLca();
for(int i=0;i<Q;i++){
int l,r,mod,c;
scanf("%d%d%d%d",&l,&r,&mod,&c);
int ans =mid( l, r, mod, c);
printf("%d\n",ans);
}
}
int main(){
scanf("%d%d%d",&N,&M,&Q);
for(int i=0;i<M;i++){
int from,to,cost;
scanf("%d%d%d",&from,&to,&cost);
arr.push_back(edge(from,to,cost));
}
Inquery();
return 0;
}
线段树方法
同时给出两者映射的关系
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int N, M, Q;
const int MaxM = 2e5;//修正4:不能用10^5
const int MaxN = 50001;
/*边的抽象*/
struct Edge {
int from, to, cost;//起点,终点,代价
Edge(int from, int to, int cost) {
this->from = from;
this->to = to;
this->cost = cost;
}
};
bool cmp(Edge *e1, Edge *e2) {
return e1->cost < e2->cost;
}
Edge *edges[MaxM];
/*并查集*/
struct UFNode {
UFNode *parent;
UFNode() : parent(NULL) {}
};
UFNode *find(UFNode *p) {
if (p->parent == NULL)return p;
set<UFNode *> path;
while (p->parent != NULL) {
path.insert(p);
p = p->parent;
}
set<UFNode *>::iterator iter = path.begin();
while (iter != path.end()) {
(*iter)->parent = p;
iter++;//修正1.指针后移
}
return p;
}
void merge(UFNode *p1, UFNode *p2) {
find(p2)->parent = find(p1);
}
UFNode ufnodes[MaxN];//并查集的节点,一开始各自独立
/*最小树的生成及表示*/
vector<Edge *> mst[MaxN];
void buildMST() {
int cnt = 0;//已加入边的数量
for (int i = 0; i < M; ++i) {
Edge *pEdge = edges[i];
int from = pEdge->from;
int to = pEdge->to;
int cost = pEdge->cost;
if (find(&ufnodes[from]) == find(&ufnodes[to]))//这两个点已经在一棵树上,这条边不能采纳
continue;
else {
merge(&ufnodes[from], &ufnodes[to]);
cnt++;
// 将边加入到mst(邻接表)
mst[from].push_back(pEdge);
Edge *other = new Edge(to, from, cost);
mst[to].push_back(other);
if (cnt == N - 1)//构建完成
{
break;
}
}
}
}
/*lca及最值查询*/
int ff[MaxN][17];//ff[i][j]指的是标号为i的节点往根节点的方向移动2^i次达到的节点的标号 ff[i][j]=ff[ff[i][j-1]][j-1]
int mm[MaxN][17];//mm[i][j]指的是标号为i的节点往根节点的方向移动2^i次过程中的最大权
int depth[MaxN];//记录每个点在mst中的深度
int vis[MaxN];//记录某个点是否被访问过
/**
*
* @param start 开始的点标号
* @param parent 父节点标号
* @param depth 这个点的深度
*/
void dfs(int start, int parent, int d) {
depth[start] = d + 1;
vis[start] = 1;
// 先向上走
for (int i = 1; i < 17; ++i) {
ff[start][i] = ff[ff[start][i - 1]][i - 1];
mm[start][i] = max(mm[start][i - 1], mm[ff[start][i - 1]][i - 1]);
}
// 向下递归,找到所有儿子(所有邻居)
for (int i = 0; i < mst[start].size(); ++i) {
Edge *child = mst[start][i];//儿子
if (vis[child->to])continue;
ff[child->to][0] = start;
mm[child->to][0] = child->cost;
dfs(child->to, start, d + 1);
}
}
void preLca() {
ff[1][0] = 1;//定义1号节点为根节点
mm[1][0] = 0;//定义1号节点为根节点,它向上一步就没了,
dfs(1, 1, 0);
}
/*倍增法,求lca,顺便求max权重*/
int maxUsingLca(int a, int b) {
int ans = -1;
// 1.将a深度调到更深(交换)
if (depth[a] < depth[b]) {
int t = a;
a = b;
b = t;
}
//2.将a调到和b同一高度
int k = depth[a] - depth[b];//高度差
for (int i = 0; (1 << i) <= k; ++i) {//k的二进制101
if ((1 << i) & k)//k二进制的第i(从右往左)位是1
{
ans = max(ans, mm[a][i]);
a = ff[a][i];
}
}
// 至此,a和b已经在同一层上
//从最顶层开始遍历,求ab两点的lca的下一层
if (a != b) {//=========此处为重要更新=========
for (int j = 16; j >= 0; --j) {
if (ff[a][j] == ff[b][j])continue;
//从最大祖先开始,判断a,b祖先,是否相同,
// 一开始肯定相同,直到它们都跳j到最近祖先的下一层时,这个else触发
else {
ans = max(ans, mm[a][j]);
ans = max(ans, mm[b][j]);
a = ff[a][j];
b = ff[b][j];
// break;//重要更新,此处不能break
}
}
// 至此,a,b离lca还差一步
//再往上走一步就得到了lca
ans = max(ans, mm[a][0]);
ans = max(ans, mm[b][0]);
}
return ans;
}
void mid(int l, int r, int mod, int c) {
int ans = -1;
int left = l - l % mod + c;
if (left < l)left += mod;
// 遍历关注点,两两在mst中用倍增法求lca顺便求max权重
for (; left + mod <= r; left += mod) {
int l = maxUsingLca(left, left + mod);
ans = max(ans, l);
}
printf("%d\n", ans);
}
/*线段树的定义,构建,及查询*/
struct SegTree {
int l, r, maxX;
SegTree *lson, *rson;
};
int data[MaxN];//用来存储线段树的原始数据
SegTree *buildSegTree(int l, int r) {
SegTree *stree = new SegTree();
stree->l = l;
stree->r = r;
if (l == r) {
stree->maxX = data[l];
return stree;
}
int mid = (l + r) / 2;
stree->lson = buildSegTree(l, mid);
stree->rson = buildSegTree(mid + 1, r);
stree->maxX = max(stree->lson->maxX, stree->rson->maxX);
return stree;
}
int queryInSegTree(SegTree *root, int p1, int p2) {
int l = root->l;
int r = root->r;
if (p1 <= l && p2 >= r)return root->maxX;//p1,p2完全覆盖l~r的时候直接返回
int mid = (l + r) / 2;
int ans = -1;
if (p1 <= mid)ans = max(ans, queryInSegTree(root->lson, p1, p2));
if (p2 > mid)ans = max(ans, queryInSegTree(root->rson, p1, p2));
return ans;
}
void hard(int l, int r, int mod, int c, SegTree *segTrees[]) {
SegTree *tree = segTrees[mod * (mod - 1) / 2 + c + 1];
int p1 = 0;
if (l <= c)p1 = 1;
else
p1 = (l - c) % mod == 0 ? (l - c) / mod + 1 : (l - c) / mod + 2;
int p2 = (r - c) / mod;
int ans = queryInSegTree(tree, p1, p2);
printf("%d\n", ans);
}
int main(int argc, const char *argv[]) {
freopen("/Users/zhengwei/CLionProjects/lanqiaobei2019/2015_A/data10/in8.txt", "r", stdin);
freopen("/Users/zhengwei/CLionProjects/lanqiaobei2019/2015_A/data10/myout8.txt", "w", stdout);
scanf("%d %d %d", &N, &M, &Q);
for (int i = 0; i < M; ++i) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
Edge *e = new Edge(a, b, c);
edges[i] = e;
}
// 排序
sort(edges, edges + M, cmp);//修正3.排序边界
buildMST();//生成最小树
preLca();//在最小树为倍增法做预处理
int threshold = min(70, N / 3);
/*生成很多的线段树,具体来说,对小于等于70的每个mod,每个c都生成一颗线段树*/
SegTree *segTrees[threshold * (threshold + 1) / 2 + 1];
int index = 1;
// 对每个mod
for (int _mod = 1; _mod <= threshold; ++_mod) {
// 对每个余数
/* {//针对re=0,余数为0的情况
int k = 1;
// 迭代1~N中符合条件的关注点,两两连通求最大权重,存储在data中
for (; (k + 1) * _mod < N; k++) {
data[k] = maxUsingLca(k * _mod, (k + 1) * _mod);
}
segTrees[index++] = buildSegTree(1, k);
}*/
for (int re = 0; re < _mod; ++re) {
//具体来说1~N之间有多个关注点满足%mod=c的情况,把这些点两两第计算出max权重,存储在区间树的原始数据中
//并依次来生成区间树
int k = 0;
// 迭代1~N中符合条件的关注点,两两连通求最大权重,存储在data中
for (; (k + 1) * _mod + re <= N; k++) {
data[k + 1] = maxUsingLca(k * _mod + re, (k + 1) * _mod + re);
}
segTrees[index++] = buildSegTree(1, k);
}
}
for (int i = 0; i < Q; ++i) {
int l, r, mod, c;
scanf("%d %d %d %d", &l, &r, &mod, &c);
if (mod > threshold)
mid(l, r, mod, c);
else
hard(l, r, mod, c, segTrees);
}
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 50005;
int N,M,Q;
int father[MAXN];
int level[MAXN];
int depth[MAXN];
int ff[MAXN][17];
int mm[MAXN][17];
struct edge{
int from,to,cost;
edge(int from,int to,int cost): from(from),to(to),cost(cost){};
};
struct node{
int to,cost,rec;
node(int to,int cost,int rec):to(to),cost(cost),rec(rec){};
};
vector<edge> arr;
vector<node> map[MAXN];
void add_edge(int from,int to,int cost){
map[from].push_back(node(to,cost,map[to].size()));
map[to].push_back(node(from,cost,map[from].size()-1));
}
bool cmp(const edge &a,const edge &b){
return a.cost<b.cost;
}
void init(){
for(int i=1;i<=N;i++){
father[i] = i;
level[i]= 1;
}
}
int find(int u){
if(father[u]!=u){
father[u] = find(father[u]);
}
return father[u];
}
void unite(int x,int y){
x = find(x);
y = find(y);
if(x==y) return;
if(level[x]>level[y]){
father[y] = x;
}else{
father[x] = y;
if(level[x]==level[y]){
level[y]++;
}
}
}
bool same(int x,int y){
return find(x)==find(y);
}
void buildMST(){
sort(arr.begin(),arr.end(),cmp);
// for(int i=0;i<arr.size();i++){
// printf("%d %d %d \n",arr[i].from,arr[i].to,arr[i].cost);
// }
init();
for(int i=1,j=0;i<=N-1 && j<arr.size();j++){
edge e = arr[j];
if(same(e.from,e.to)) continue;
unite(e.from,e.to);
add_edge(e.from,e.to,e.cost);
i++;
}
}
void dfs(int start,int parent,int d){
depth[start] = d;
for(int i=1;i<=16;i++){
ff[start][i] = ff[ff[start][i-1]][i-1];
mm[start][i] = max(mm[start][i-1],mm[ff[start][i-1]][i-1]);
}
for(int i=0;i<map[start].size();i++){
node nn = map[start][i];
if(nn.to == parent) continue;
ff[nn.to][0] = start;
mm[nn.to][0] = nn.cost;
dfs(nn.to,start,d+1);
}
}
int usingLca(int a,int b){
if(depth[a]<depth[b]){
swap(a,b);
}
int k = depth[a] - depth[b];
int ans = -1;
for(int i=0;(1<<i)<=k;i++){
if((k>>i)&1){
ans = max(ans,mm[a][i]);
a = ff[a][i];
}
}
for(int i=16;i>=0;i--){
if(ff[a][i] == ff[b][i])continue;
ans = max(ans,mm[a][i]);
ans = max(ans,mm[b][i]);
a = ff[a][i];
b = ff[b][i];
}
ans = max(ans,mm[a][0]);
ans = max(ans,mm[b][0]);
return ans;
}
void buildLca(){
ff[1][0] = 1;
mm[1][0] = 0;
dfs(1,-1,1);
}
int mid(int left,int right,int mod,int c){
int l = left-left%mod +c;
if(l<left) l+=mod;
int ans = -1;
for(int i=l;i+mod<=right;i+=mod){
ans = max(ans,usingLca(i,i+mod));
}
return ans;
}
int data[MAXN];
//int segTree[MAXN*4];
struct segtree{
int l,r,max;
segtree* lson ;
segtree* rson ;
};
segtree *buildsegTree(int l,int r){
segtree * tree = new segtree();
tree->l = l; tree->r = r;
if(l==r) {
tree->max = data[l];
return tree;
}
int mid = (l+r)/2;
tree->lson = buildsegTree(l,mid);
tree->rson = buildsegTree(mid+1,r);
tree->max = max(tree->lson->max,tree->rson->max);
return tree;
}
int inquerySegTree(int p1,int p2,segtree *tree){
int l = tree->l;
int r = tree->r;
if(p1 <=l && p2>=r) return tree->max;
int mid = (l+r)/2;
int ans = -1;
if(p1<=mid)ans = max(ans,inquerySegTree(p1,p2,tree->lson));
if(p2>mid) ans = max(ans,inquerySegTree(p1,p2,tree->rson));
return ans;
}
hard(int left,int right,int mod,int c,segtree *tree[]){
int id = (mod*(mod-1)/2+c+1);
int p1 = 0;
if(left<=c) p1 = 1;
else p1 = (left-c)%mod==0 ?(left-c)/mod+1:(left-c)/mod+2;
int p2 = (right-c)/mod;
int ans = inquerySegTree(p1,p2,tree[id]);
return ans;
}
int Inquery(){
buildMST();
buildLca();
int threshold = min(70,N/3);
segtree * trees[threshold*(threshold+1)/2+1];
int index = 1;
for(int mod_ = 1;mod_<=threshold;mod_++){
for(int re = 0;re<mod_;re++){
int k=0;
for(;(k+1)*mod_+re<=N;k++){
data[k+1] = usingLca((k)*mod_+re,(k+1)*mod_+re);
}
trees[index++] = buildsegTree(1,k);
}
}
for(int i=0;i<Q;i++){
int l,r,mod,c;
scanf("%d%d%d%d",&l,&r,&mod,&c);
int ans;
if(mod>threshold){
ans =mid( l, r, mod, c);
}else{
ans =hard(l,r,mod,c,trees);
}
printf("%d\n",ans);
}
}
int main(){
scanf("%d%d%d",&N,&M,&Q);
for(int i=0;i<M;i++){
int from,to,cost;
scanf("%d%d%d",&from,&to,&cost);
arr.push_back(edge(from,to,cost));
}
Inquery();
return 0;
}