Submission #545252

#	Time	Username	Problem	Language	Result	Execution time	Memory
545252		amunduzbaev	Bridges (APIO19_bridges)	C++17	13 / 100	3074 ms	9136 KiB

bridges

#include "bits/stdc++.h"
using namespace std;

#define ar array
const int N = 5e4 + 5;
vector<int> edges[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> e(m);
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		e[i] = {a, b, c};
	}
	
	int q; cin>>q;
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int j, w; cin>>j>>w;
			e[--j][2] = w;
		} else {
			int a, w; cin>>a>>w;
			for(int i=0;i<m;i++){
				if(e[i][2] >= w){
					edges[e[i][0]].push_back(e[i][1]);
					edges[e[i][1]].push_back(e[i][0]);
				}
			}
			
			int cnt = 0;
			vector<int> used(n + 1);
			function<void(int)> dfs = [&](int u){
				used[u] = 1, cnt++;
				for(auto x : edges[u]){
					if(!used[x]) dfs(x);
				}
			};
			dfs(a);
			cout<<cnt<<"\n";
			for(int i=1;i<=n;i++) edges[i].clear();
		}
	}
}

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