Submission #1044620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044620		vjudge1	다리 (APIO19_bridges)	C++17	14 / 100	312 ms	45252 KiB

bridges

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int32_t main(){
	int n,m;
	cin>>n>>m;
	vector<pair<int,pair<int,int>>>edges,edge(m);
	for(int i=0;i<m;i++){
		int u,v,d;
		cin>>u>>v>>d;
		u--,v--;
		edges.pb({d,{u,v}});
		edge[i]={d,{u,v}};
	}
	auto find_mst=[&](vector<pair<int,pair<int,int>>>&edges,vector<vector<pair<int,int>>>&adj,vector<vector<pair<int,int>>>&par,vector<int>&sub)->void{
		for(int i=0;i<n;i++){
			adj[i].clear();
		}
		sort(all(edges),[](pair<int,pair<int,int>>&a,pair<int,pair<int,int>>&b){return a.ff>b.ff;});
		vector<int>fa(n),id(n);
		for(int i=0;i<n;i++){
			fa[i]=i;
			id[i]=i;
			sub[i]=1;
		}
		int cnt=n;
		auto find=[&](int x,auto&& find)->int{
			if(fa[x]==x)return x;
			return fa[x]=find(fa[x],find);
		};
		auto merge=[&](int x,int y,int z)->bool{
			int a=find(x,find),b=find(y,find);
			if(a==b)return false;
			par[cnt][0]={-1,-1};
			par[id[a]][0]={z,cnt};
			par[id[b]][0]={z,cnt};
			sub[cnt]=sub[id[a]]+sub[id[b]];
			fa[a]=b;
			id[b]=cnt;
			cnt++;
			return true;
		};
		for(auto i:edges){
			if(merge(i.ss.ff,i.ss.ss,i.ff)){
				adj[i.ss.ff].pb({i.ss.ss,i.ff});
				adj[i.ss.ss].pb({i.ss.ff,i.ff});
			}
		}
		return;
	};
	int l=__lg(2*n)+1;
	vector<vector<pair<int,int>>>adj(n),par(2*n,vector<pair<int,int>>(l));
	vector<int>sub(2*n);
	find_mst(edges,adj,par,sub);
	for(int j=1;j<l;j++){
		for(int i=0;i<2*n-1;i++){
			if(par[i][j-1].ss==-1)par[i][j]={-1,-1};
			else{
				par[i][j].ff=min(par[i][j-1].ff,par[par[i][j-1].ss][j-1].ff);
				par[i][j].ss=par[par[i][j-1].ss][j-1].ss;
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			exit(0);
		}
		else{
			int s,w;
			cin>>s>>w;
			s--;
			for(int i=l-1;i>=0;i--){
				if(par[s][i].ss!=-1 && par[s][i].ff>=w){
					s=par[s][i].ss;
				}
			}
			cout<<sub[s]<<endl;
		}
	}
}

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