Submission #2121600

---

Source Code Expand

#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define N 200005
#define LOGN 20
using namespace std;

struct Edge{
	
    int u, v, w;
    Edge(int _u, int _v, int _w){ u = _u; v = _v; w = _w; }
    Edge(){}
	
    void read(){ scanf("%d%d", &u, &v); u--; v--; }
    void print(){ printf("%d %d %d\n", u, v, w); }
};

Edge E[N];
bool operator <(const Edge &e1, const Edge &e2){ return e1.w < e2.w; }

int P[N], size[N], heavyEdge[N], n, m, nodes;

int Find(int x){

    if(x == P[x])return x;
    return P[x] = Find(P[x]);
}

void Union(int x, int y){ //First one will be the superset any time
	
    x = Find(x);
    y = Find(y);
	
    P[y] = x;
    size[x] += size[y];
}

vector<Edge> GetMinimumSpanningTree(){

	vector<Edge>ans;
	int u, v, w;
	
	for(int i = 0; i < n; i++)P[i] = i;
	//sort(E, E + m);
	
	for(int i = 0; i < m; i++){
	
		u = E[i].u;
		v = E[i].v;
		w = E[i].w;
		
		if(Find(u) != Find(v))Union(u, v), ans.pb(E[i]);
	}
	
	return ans;
}

int Next[LOGN][N];
int Explore(int u, int v, int heaviest){

	int supersetSize = 0;
	
	for(int i = LOGN - 1; i >= 0; i--){
		
		if(Next[i][u] == -1 || heavyEdge[Next[i][u]] > heaviest)continue;
		u = Next[i][u];
	}
	
	supersetSize += size[u];
	for(int i = LOGN - 1; i >= 0; i--){
		
		if(Next[i][v] == -1 || heavyEdge[Next[i][v]] > heaviest)continue;
		v = Next[i][v];
	}
	
	if(u != v)supersetSize += size[v];
	return supersetSize;
}
int main(){

	scanf("%d%d", &n, &m);
	
	for(int i = 0; i < m; i++)E[i].read(), E[i].w = i + 1;
	vector<Edge>MST = GetMinimumSpanningTree();
	
	//for(int i = 0; i < n - 1; i++)MST[i].print();
	
	nodes = n;
	for(int i = 0; i < n; i++)P[i] = i, size[i] = 1;
	for(int i = n; i < 2 * n; i++)P[i] = i, size[i] = 0;
	
	int u, v, w;
	memset(Next, -1, sizeof Next);
	
	for(int i = 0; i < MST.size(); i++){
	
		u = MST[i].u;
		v = MST[i].v;
		w = MST[i].w;
		
		Next[0][Find(u)] = nodes;
		Next[0][Find(v)] = nodes;
		
		Union(nodes, Find(u));
		Union(nodes, Find(v));

		heavyEdge[nodes] = w;
		nodes++;
	}
	
	//for(int i = 0; i < nodes; i++)printf("node: %d | parent: %d | size: %d | heavyEdge: %d\n", i, Next[0][i], size[i], heavyEdge[i]);
	
	for(int j = 1; j < LOGN; j++){
		for(int i = 0; i < nodes; i++){
		
		
			if(Next[j - 1][i] == -1)continue;
			Next[j][i] = Next[j - 1][Next[j - 1][i]];
		}
	}
	
	int q, z;
	scanf("%d", &q);
	
	for(int i = 0; i < q; i++){
	
		scanf("%d%d%d", &u, &v, &z);
		u--; v--;
		
		int lo = 1, hi = m, me;
		while(lo < hi){
			
			me = lo + (hi - lo)/2;
			if(Explore(u, v, me) >= z)hi = me;
			else lo = me + 1;
		}
		
		printf("%d\n", lo);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:82:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:124:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
                 ^
./Main.cpp:128:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &z);
                              ^
./Main.cpp: In member function ‘void Edge::read()’:
./Main.cpp:15:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     void read(){ scanf("%d%d", &u, &v); u--; v--; }
                                       ^

Judge Result