Submission #597561

#	Time	Username	Problem	Language	Result	Execution time	Memory
597561		WongChun1234	Bridges (APIO19_bridges)	C++14	0 / 100	1341 ms	27340 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int N=150050;
int n,m,q,u[N],v[N],w[N],ans,t,a,b,lift[20][N],ch[2][N],sz[N],par[N],val[N],rt=1,rpar[20][N];
bool vis[N];
vector<int> adj[N];
vector<pair<int,pair<int,int>>> srt;
int find(int u){
	return (par[u]==u)?u:par[u]=find(par[u]);
}
void dfs(int nde,int par){
	lift[0][nde]=val[par];
	for (int i=1;i<20;i++){
		rpar[i][nde]=rpar[i-1][rpar[i-1][nde]];
		lift[i][nde]=val[rpar[i][nde]];
	}
	cerr<<nde<<":"<<val[nde]<<"::"<<ch[0][nde]<<","<<ch[1][nde]<<"\n";
	if (nde>n){
		dfs(ch[0][nde],nde);
		dfs(ch[1][nde],nde);
	}
}
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>u[i]>>v[i]>>w[i];
		srt.push_back({-w[i],{u[i],v[i]}});
	}
	for (int i=1;i<=n;i++) sz[i]=1,val[i]=INT_MAX;
	sort(srt.begin(),srt.end());
	int cnt=n;
	for (int i=1;i<2*n;i++) par[i]=i;
	for (auto i:srt){
		if (find(i.second.first)==find(i.second.second)) continue;
		ch[0][++cnt]=find(i.second.first);
		ch[1][cnt]=find(i.second.second);
		sz[cnt]=sz[find(i.second.first)]+sz[find(i.second.second)];
		val[cnt]=-i.first;
		rpar[0][find(i.second.first)]=rpar[0][find(i.second.second)]=cnt;
		par[find(i.second.first)]=par[find(i.second.second)]=cnt;
		rt=cnt;
	}
	rpar[0][rt]=rt;
	dfs(rt,rt);
	cin>>q;
	while (q--){
		cin>>t>>a>>b;
		if (t==1) continue;
		for (int i=19;i>=0;i--){
			if (val[rpar[i][a]]>=b) a=rpar[i][a];
		}
		cout<<sz[a]<<"\n";
	}
}
/*
7 8
1 2 1
2 3 1
3 4 2
4 5 5
5 6 5
6 1 3
6 7 1
7 2 5
0
*/

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