Submission #597571

#	Time	Username	Problem	Language	Result	Execution time	Memory
597571		WongChun1234	Bridges (APIO19_bridges)	C++14	14 / 100	201 ms	7916 KiB

bridges

#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";
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27