Submission #597571

#TimeUsernameProblemLanguageResultExecution timeMemory
597571WongChun1234Bridges (APIO19_bridges)C++14
14 / 100
201 ms7916 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=150050;
int n,m,q,u,v,w,t,a,b,sz[N],par[N],ans[N];
vector<pair<int,pair<int,int>>> srt;
int find(int u){
	return (par[u]==u)?u:par[u]=find(par[u]);
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>u>>v>>w;
		srt.push_back({-w,{u,v}});
	}
	cin>>q;
	for (int i=1;i<=q;i++){
		cin>>t>>a>>b;
		if (t==2) srt.push_back({-b+1,{-a,-i}});
	}
	for (int i=1;i<=n;i++) sz[i]=1,par[i]=i;
	sort(srt.begin(),srt.end());
	for (auto i:srt){
		if (i.second.second>0){
			if (find(i.second.first)==find(i.second.second)) continue;
			sz[find(i.second.first)]+=sz[find(i.second.second)];
			par[find(i.second.second)]=find(i.second.first);
		}else{
			ans[-i.second.second]=sz[find(-i.second.first)];
		}
	}
	for (int i=1;i<=q;i++) if (ans[i]) cout<<ans[i]<<"\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...
#Verdict Execution timeMemoryGrader output
Fetching results...