Submission #1174540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174540		tkm_algorithms	Bridges (APIO19_bridges)	C++20	13 / 100	3096 ms	10536 KiB

bridges

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 1e7;

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, qq; cin >> n >> m;
	
	vector<pair<int, int>> g[n+1];
	vector<pair<int, int>> qu(m+1), qu2(m+1);
	for (int i = 0; i < m; ++i) {
		int a, b, w; cin >> a >> b >> w;
		qu[i+1] = {sz(g[a]), sz(g[b])};
		qu2[i+1] = {a, b};
		g[a].push_back({b, w});
		g[b].push_back({a, w});
	}
	
	cin >> qq;
	queue<int> q;
	vector<int> vis(n+1);
	for (int _ = 0; _ < qq; ++_) {
		int tp; cin >> tp;
		if (tp == 1) {
			int bj, rj; cin >> bj >> rj;
			int a = qu[bj].first, b = qu[bj].second;
			int u = qu2[bj].first, v = qu2[bj].second;
			g[u][a].second = rj; g[v][b].second = rj;
		} else {
			int sj, wj; cin >> sj >> wj;
			vis[sj] = 1;
			q.push(sj);
			int ans = 1;
			while (!q.empty()) {
				int u = q.front();
				q.pop();
				
				for (auto i: g[u]) {
					if (vis[i.first] == 1 || i.second < wj)continue;
					vis[i.first] = 1;
					//if (_ == 2)cout << i.first << " ";
					q.push(i.first);
					ans += 1;
				}
			}
			cout << ans << nl;
			for (int i = 1; i <= n; ++i)vis[i] = 0;
		}
	}
	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