Submission #1350753

#TimeUsernameProblemLanguageResultExecution timeMemory
1350753jumpDrivers (BOI24_drivers)C++20
100 / 100
210 ms18984 KiB
#include <bits/stdc++.h>
#define int long long
int n,m,u;
int dsu[200010];
bool ans[200010];
int find(int num){
	if(dsu[num]==num)return num;
	else return dsu[num]=find(dsu[num]);
}
void unionS(int a,int b){
	int A = find(a);
	int B = find(b);
	dsu[A]=B;
}
signed main() {
	std::cin >> n >> m >> u;
	std::vector<std::pair<int,std::pair<int,int>>> link;
	std::vector<std::pair<std::pair<int,int>,std::pair<int,int>>> query;
	for(int i=0;i<=n;i++)dsu[i]=i;
	for(int i=0;i<m;i++){
		int a,b,c;
		std::cin >> a >> b >> c;
		link.push_back({c,{a,b}});
	}
	std::sort(link.begin(),link.end());
	for(int i=0;i<u;i++){
		int a,b,c;
		std::cin >> a >> b >> c;
		query.push_back({{c,i},{a,b}});
	}
	std::sort(query.begin(),query.end());
	int handle=0;
	int handle2=0;
	while(handle<query.size()){
		while(handle2<link.size()&&link[handle2].first<=query[handle].first.first){
			unionS(link[handle2].second.first,link[handle2].second.second);
			handle2+=1;
		}
		ans[query[handle].first.second]=(find(query[handle].second.first)==find(query[handle].second.second));
		handle+=1;
	}
	for(int i=0;i<u;i++){
		if(ans[i])std::cout << "TAIP\n";
		else std::cout << "NE\n";
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...