Submission #2120788

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

const int MAX_N=100000;
int N,M,Q;

int par[MAX_N]; //　親
int rnk[MAX_N]; // rank, 木の深さ
int num[MAX_N];

// N要素で初期化
void init(){
  for(int i=0;i<N;i++){
    par[i]=i;
    rnk[i]=0;
    num[i]=1;
  }
}

// 木の根を求める
int find(int x){
  if (par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

// ｘとｙの属する集合を併合
void unite(int x, int y){
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rnk[x] < rnk[y]){
    par[x] = y;
    num[y]+=num[x];
  }else{
    par[y] = x;
    num[x]+=num[y];
    if (rnk[x] == rnk[y]) rnk[x]++;
  }
}

// ｘとｙが同じ集合に属するかどうか
bool same(int x, int y){
  return find(x) == find(y);
}


int main(){
  cin>>N>>M;
  init();
  vector<pair<int,pair<int,int>>> v(M);
  for(int i=0;i<M;i++){
    int a,b,y;
    cin>>a>>b>>y;
    a--, b--;
    v[i]={y,{a,b}};
  }
  sort(v.rbegin(),v.rend());
  cin>>Q;
  vector<pair<int,pair<int,int>>> p(Q);
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    a--;
    p[i]={b,{i,a}};
  }
  sort(p.rbegin(),p.rend());
  int ind=0;
  int ans[Q]={};
  for(int i=0;i<Q;i++){
    int w=p[i].first;
    int from=p[i].second.second;
    for(int j=ind;j<M;j++){
      int y=v[j].first;
      int a=v[j].second.first;
      int b=v[j].second.second;
      if(y>w){
        if(!same(a,b)) unite(a,b);
      }else break;
      ind++;
    }
    int root=find(from);
    ans[p[i].second.first]=num[root];
  }
  for(int i=0;i<Q;i++) cout<<ans[i]<<endl;
  return 0;
}

Submission Info

Judge Result