Submission #933970

#	Time	Username	Problem	Language	Result	Execution time	Memory
933970		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3065 ms	9256 KiB

bridges

// Problem: B - Bridges
// Contest: Virtual Judge - Tercer examen de práctica PES Febrero 2024
// URL: https://vjudge.net/contest/612365#problem/B
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Start: 26-02-2024 09:34:32

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

using ll  = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;

#define gcd(x, y) __gcd(x, y)
#define mcm(x, y) abs((x) * (y)) / gcd(x, y)
#define all(x)    begin(x), end(x)
#define pb(x)     push_back(x)
#define endl      '\n'

void solve1() {
	ll n, m;
	cin >> n >> m;
	vector<vector<pll>> g(n + 1);
	vector<ll>          d(m + 1);
	for (int i = 1; i <= m; i++) {
		ll a, b, w;
		cin >> a >> b >> w;
		d[i] = w;
		g[a].pb(make_pair(b, i));
		g[b].pb(make_pair(a, i));
	}

	ll q;
	cin >> q;
	while (q--) {
		ll op, a, b;
		cin >> op >> a >> b;
		if (op == 1) {
			d[a] = b;
			continue;
		}

		ll           ans = 0;
		queue<ll>    q;
		vector<bool> vis(n + 1);
		q.push(a);

		while (q.size()) {
			ll curr = q.front();
			q.pop();
			if (vis[curr]) continue;
			vis[curr] = true;
			ans++;

			for (pll& nei : g[curr])
				if (!vis[nei.first] && b <= d[nei.second])
					q.push(nei.first);
		}

		cout << ans << endl;
	}
}

int main() {
#ifdef DEBUG
	std::cout << std::unitbuf;
#endif

	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	solve1();

	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