Submission #2526470

---

Source Code Expand

#include <stack>
#include <queue>
#include <cstdio>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
 
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n0,n) for(int i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
#define INF (1<<29)
#define test cout << "test" << endl;

int unionf[100010];
int ranks[100010];

int init(int a){
	rep(i,a){
		unionf[i+1]=i+1;
		ranks[i+1]=1;
	}
}

int find(int a){
	return (unionf[a]==a)? a:unionf[a]=find(unionf[a]);
}

void unite(int a,int b){
	a=find(a);
	b=find(b);

	if(ranks[a]>ranks[b]){
		unionf[b]=a;
	}
	else {
		unionf[a]=b;
		if(ranks[a]==ranks[b])
			ranks[b]++;
	}
	return ;
}



int main (){
	int NNN,MMM;
	cin >> NNN >> MMM;

	vector <pair<int,pair<int,int>>> bridges;
	vector <pair<int,pair<int,int>>> people;	
	pair <int ,int > tempair;
	int tempa,tempb;
	int tempyear;
	rep(i,MMM){
		cin >> tempa >> tempb >>tempyear;
		tempair = make_pair(tempa,tempb);
		bridges.push_back(make_pair(tempyear,tempair));
	}
	sort(bridges.begin(),bridges.end());

	int QQQ;
	cin >> QQQ;

	rep(i,QQQ){
		cin >> tempa >>tempyear;
		tempair = make_pair(i,tempa);
		people.push_back(make_pair(tempyear,tempair));
	}
	sort(people.begin(),people.end());

	int answers[QQQ+1];

	int year_people; // 今都市数を数えたい人の番号（入力の順番）
	int year_bridges;//今年を数えたい人の許容年
	int number_of_people; //
	int toshi_people;
	int count_toshi;
	int loop_people=people.size()-1;
	int loop_bridges=bridges.size()-1;
	bool bridge_check=true;

	init(NNN);

	while(1){
		year_people = people[loop_people].first;
		number_of_people = people[loop_people].second.first;
		toshi_people = people[loop_people].second.second;

	//	cout << "year_people =" <<  year_people << "number_of_people =" <<number_of_people  <<"toshi_people =" <<toshi_people <<endl;

		while(1){

			year_bridges = bridges[loop_bridges].first;
	//		cout << year_bridges <<endl;
			
			if(year_bridges >year_people){
				unite(bridges[loop_bridges].second.first,bridges[loop_bridges].second.second);
		//		cout <<bridges[loop_bridges].second.first <<" " <<bridges[loop_bridges].second.second <<endl;
 				loop_bridges --;	
			}
			else{ 
				break;
			}



			
			if(loop_bridges<0) break;
		}

		count_toshi=0;

		rep(i,NNN){
			if(find(unionf[i+1])==find(toshi_people)){
				count_toshi++;
			}
		}

		answers[number_of_people]=count_toshi;
		
		loop_people--;
		
		if(loop_people<0) break;
	}

	rep(i,QQQ){
		cout << answers[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result