Submission #1173924

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173924		stdfloat	Bridges (APIO19_bridges)	C++17	13 / 100	3095 ms	6016 KiB

bridges

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

using ll = long long;

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

	int n, m;
	cin >> n >> m;

	vector<pair<int, int>> E[n];
	vector<int> u(m), v(m), D(m);
	for (int i = 0; i < m; i++) {
		cin >> u[i] >> v[i] >> D[i]; u[i]--; v[i]--;
		
		E[u[i]].push_back({v[i], i});
		E[v[i]].push_back({u[i], i});
	}

	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
	
		if (t == 1) {
			int b, r;
			cin >> b >> r; b--;

			D[b] = r;
		}
		else {
			int s, w;
			cin >> s >> w; s--;

			queue<int> q;
			vector<bool> vis(n);
			q.push(s); vis[s] = true;
			while (!q.empty()) {
				int x = q.front(); q.pop();

				for (auto [i, d] : E[x]) {
					if (!vis[i] && w <= D[d]) {
						q.push(i);
						vis[i] = true;
					}
				}
			}

			cout << count(vis.begin(), vis.end(), true) << '\n';
		}
	}
}

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