제출 #1044620

#제출 시각아이디문제언어결과실행 시간메모리
1044620vjudge1다리 (APIO19_bridges)C++17
14 / 100
312 ms45252 KiB
#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;
		}
	}
}
#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...