Submission #3223071

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n,m,q,uni[N],ans[N],sz[N];
struct edge {
  int a,b;
} edg[N];
int getfa(int pos) {
  return pos == uni[pos] ? pos : uni[pos] = getfa(uni[pos]);
}
void join(int a,int b) {
  a = getfa(a);
  b = getfa(b);
  if (a == b) return;
  if (sz[a] > sz[b]) swap(a,b);
  uni[a] = b;
  sz[b] += sz[a];
}
int calc(int a,int b) {
  a = getfa(a), b = getfa(b);
  if (a == b) return sz[a];
  return sz[a] + sz[b];
}
struct data {
  int x,y,z,id;
};
struct Divide {
  int l,r,ansl,ansr;
};
vector<data> que[2];
vector<Divide> Div[2];
int main() {
  int x,y,z;
  scanf("%d%d",&n,&m);
  for (int i = 1 ; i <= m ; ++ i) {
    scanf("%d%d",&x,&y);
    edg[i] = (edge) {x,y};
  }
  scanf("%d",&q);
  for (int i = 1 ; i <= q ; ++ i) {
    scanf("%d%d%d",&x,&y,&z);
    que[0].push_back((data) {x,y,z,i});
  }
  Div[0].push_back((Divide) {0,q-1,0,n});
  int p = 0;
  while (Div[p].size()) {
    int cur = 1;
    Div[p^1].clear();
    que[p^1].clear();
    for (int i = 1 ; i <= n ; ++ i)
      uni[i] = i, sz[i] = 1;
    for (int i = 0 ; i < (int)Div[p].size() ; ++ i) {
      int num = 0;
      if (Div[p][i].ansl == Div[p][i].ansr) {
	for (int j = Div[p][i].l ; j <= Div[p][i].r ; ++ j)
	  ans[que[p][j].id] = Div[p][i].ansl;
	continue;
      }
      int mid = (Div[p][i].ansl + Div[p][i].ansr) >> 1;
      for ( ; cur <= mid ; ++ cur)
	join(edg[cur].a,edg[cur].b);
      for (int j = Div[p][i].l ; j <= Div[p][i].r ; ++ j)
	if (calc(que[p][j].x,que[p][j].y) >= que[p][j].z)
	  que[p^1].push_back(que[p][j]), ++ num;
      if (num) Div[p^1].push_back((Divide) {(int)que[p^1].size()-num,(int)que[p^1].size()-1,Div[p][i].ansl,mid});
      num = 0;
      for (int j = Div[p][i].l ; j <= Div[p][i].r ; ++ j)
	if (calc(que[p][j].x,que[p][j].y) < que[p][j].z)
	  que[p^1].push_back(que[p][j]), ++ num;
      if (num) Div[p^1].push_back((Divide) {(int)que[p^1].size()-num,(int)que[p^1].size()-1,mid+1,Div[p][i].ansr});
    }
    p ^= 1;
  }
  for (int i = 1 ; i <= q ; ++ i)
    printf("%d\n",ans[i]);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:34:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^
./Main.cpp:36:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&x,&y);
                        ^
./Main.cpp:39:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
                 ^
./Main.cpp:41:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&x,&y,&z);
                             ^

Judge Result