Submission #1031726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031726		Muhammet	Bridges (APIO19_bridges)	C++17	13 / 100	94 ms	13648 KiB

bridges

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

#define ll long long int
#define sz(x) (int)x.size()
#define ff first
#define ss second

const ll N = 300005;
const ll M = 1e9 + 7;

int T, n, a[N], b[N], c[N], q, s[N], w[N], t[N], d[N], r[N], ans, vis[N], m;

vector <pair<int,int>> v[N];

void dfs(int x, int y){
	vis[x] = 1;
	ans++;
	for(auto i : v[x]){
		if(vis[i.ff] == 0 and i.ss >= y){
			dfs(i.ff,y);
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1){
			cin >> d[i] >> r[i];
		}
		else {
			cin >> s[i] >> w[i];
		}
	}

	if(n <= 1000 and m <= 1000 and q <= 10000){
		for(int i = 1; i <= q; i++){
			for(int j = 1; j <= n; j++){
				v[j].clear();
				vis[j] = 0;
			}
			if(t[i] == 1){
				c[d[i]] = r[i];
			}
			else {
				for(int j = 1; j <= m; j++){
					v[a[j]].push_back({b[j],c[j]});
					v[b[j]].push_back({a[j],c[j]});
				}
				ans = 0;
				dfs(s[i],w[i]);
				cout << ans << '\n';
			}
		}
	}

	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