Submission #276063

#	Time	Username	Problem	Language	Result	Execution time	Memory
276063		groeneprof	Bridges (APIO19_bridges)	C++14	13 / 100	3059 ms	8184 KiB

bridges

#include <bits/stdc++.h>

#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(b); i++)
#define F(i,n) FR(i,0,n)

const int debug = 0;

using namespace std;

vector<pair<int,int> > edges;
vector<int> weights;
int n, m, q;

vector<vector<pair<int,int> > > graph;
vector<int> par;

int root(int a){
	if(par[a] == a) return a;
	return par[a] = root(par[a]);
}

void merge(int a, int b){
	if(rand()%2) swap(a,b);
	par[root(a)] = root(b);
}

void kruskal(){
	vector<pair<int,pair<int,int> > > sorted(m);
	F(i,m){
		sorted[i] = {weights[i], edges[i]};
	}
	sort(sorted.rbegin(),sorted.rend());
	par.resize(n);
	F(i,n) par[i] = i;
	graph.assign(n,{});
	for(auto e : sorted){
		if(root(e.second.first)!=root(e.second.second)){
			H(e.second.first);
			H(e.second.second);
			H(e.first);
			H(root(e.second.first));
			H(root(e.second.second));
			
			merge(e.second.first,e.second.second);
			graph[e.second.first].push_back({e.second.second, e.first});
			graph[e.second.second].push_back({e.second.first, e.first});
		}
	}
}

int dfs(int u, int p, int w){
	int a = 1;
	for(pair<int,int> v : graph[u]) if(v.first!=p && v.second>=w){
		a+=dfs(v.first,u,w);
	}
	return a;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	edges.resize(m);
	weights.resize(m);
	F(i,m){
		cin>>edges[i].first>>edges[i].second>>weights[i];
		edges[i].first--;
		edges[i].second--;
	}
	kruskal();

	cin>>q;
	F(i,q){
		int type;
		cin>>type;
		if(type==1){
			int a, b;
			cin>>a>>b;
			a--;
			weights[a] = b;
			kruskal();
		}
		else{
			int a, b;
			cin>>a>>b;
			a--;
			cout<<dfs(a,a,b)<<endl;
		}
	}

	return 0;
}

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