Submission #558689

#	Time	Username	Problem	Language	Result	Execution time	Memory
558689		heavylightdecomp	Bridges (APIO19_bridges)	C++14	0 / 100	130 ms	5332 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int mxN = 50005, mxM = 100005;
set<pair<int,int>> graph[mxN];
tuple<int,int,int> bridge[mxM];
bool seen[mxN];
int cnt;
void dfs(int x, int weight) {
	if(seen[x]) return;
	cnt++, seen[x] = 1;
	for(auto edge : graph[x]) {
		if(edge.first < weight) continue;
		dfs(edge.second, weight);
	}
}
signed main() {
	//freopen("bridge.in", "r", stdin);
	//freopen("bridge.out", "w", stdout);
	int n, m; cin >> n >> m;
	if(n > 1000) exit(-1);
	for(int i = 1; i <= m; i++) {
		int u, v, d; cin >> u >> v >> d;
		graph[u].insert({d,v});
		graph[v].insert({d,u});
		bridge[i] = {u,v,d};
	}
	int q; cin >> q;
	for(int g = 0; g < q; g++) {
		int t; cin >> t;
		if(t==1) {
			int b, r; cin >> b >> r;
			int u,v,d; tie(u,v,d) = bridge[b];
			assert(graph[u].count({d,v}) && graph[v].count({d,u}));
			graph[u].erase({d,v});
			graph[v].erase({d,u});
			graph[u].insert({r,v});
			graph[v].insert({r,u});
			bridge[b] = {u,v,r};
		} else {
			memset(seen, 0, sizeof seen);
			cnt = 0;
			int s, w; cin >> s >> w;
			dfs(s,w);
			cout << cnt << '\n';
		}
	}
}

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