Submission #1044595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044595		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3064 ms	11496 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)->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);
		for(int i=0;i<n;i++){
			fa[i]=i;
		}
		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)->bool{
			int a=find(x,find),b=find(y,find);
			if(a==b)return false;
			fa[a]=b;
			return true;
		};
		for(auto i:edges){
			if(merge(i.ss.ff,i.ss.ss)){
				adj[i.ss.ff].pb({i.ss.ss,i.ff});
				adj[i.ss.ss].pb({i.ss.ff,i.ff});
			}
		}
		return;
	};
	vector<vector<pair<int,int>>>adj(n);
	find_mst(edges,adj);
	int q;
	cin>>q;
	while(q--){
		int t;
		cin>>t;
		if(t==1){
			int b,r;
			cin>>b>>r;
			b--;
			int ind=find(all(edges),edge[b])-edges.begin();
			edges[ind].ff=r;
			edge[b].ff=r;
			find_mst(edges,adj);
		}
		else{
			int s,w;
			cin>>s>>w;
			s--;
			int ans=0;
			auto dfs=[&](int node,int p,auto&& dfs)->void{
				ans++;
				for(auto i:adj[node]){
					if(i.ss<w || i.ff==p)continue;
					dfs(i.ff,node,dfs);
				}
				return;
			};
			dfs(s,-1,dfs);
			cout<<ans<<endl;
		}
	}
}

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