Submission #933969

#TimeUsernameProblemLanguageResultExecution timeMemory
933969vjudge1Bridges (APIO19_bridges)C++17
0 / 100
3084 ms10332 KiB
// 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(n + 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...