Submission #1244522

---

Source Code Expand

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <cstdio>
#include <math.h>
#include <utility>
#include <list>
#include <functional>
#include <queue>
using namespace std;

#define ll long long
#define vecint vector<int>
#define Pii pair<int, int>

#define REP(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define print(a) cout << a << endl

#define MOD 1000000007
#define NIL -1

int N,M,Q;

int par[100000];
int depth[100000];
int cnt[100000];

vector<pair<int,pair<int,int>>> e;

vector<pair<int,pair<int,int>>> q;

int ans[100000];

void init(int n){
    rep(i,n){
        par[i]=i;
        depth[i]=0;
        cnt[i]=1;
    }
}

int find(int x){
    if(par[x]==x) return x;
    else return par[x]=find(par[x]);
}

void unit(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(depth[x]>depth[y]){
        par[y]=x;
        cnt[x]+=cnt[y];
    }else{
        par[x]=y;
        if(depth[x]==depth[y]) depth[y]++;
        cnt[y]+=cnt[x];
    }
}


void solve(){
    init(N);
    sort(e.begin(),e.end());
    sort(q.begin(),q.end());
    reverse(e.begin(),e.end());
    reverse(q.begin(),q.end());
    int j=0;
    rep(i,Q){
        while(e[j].first>q[i].first) {
//            printf("cost%d:%d cost%d:%d\n", j,e[j].first, i,q[i].first);
            unit(e[j].second.first, e[j].second.second);
            j++;
        }
        ans[q[i].second.second]=cnt[find(q[i].second.first)];
    }
    rep(i,Q){
        print(ans[i]);
    }
    return;
}



int main(){
    cin>>N>>M;
    rep(i,M){
        int x,y,cost;
        cin>>x>>y>>cost;
        x--;y--;
        e.push_back(make_pair(cost,make_pair(x,y)));
    }
    cin>>Q;
    rep(i,Q){
        int start,cost;
        cin>>start>>cost;
        start--;
        q.push_back(make_pair(cost,make_pair(start,i)));
    }
    solve();
    return 0;
}

Submission Info

Judge Result