Submission #382961

#	Time	Username	Problem	Language	Result	Execution time	Memory
382961		milleniumEeee	Bridges (APIO19_bridges)	C++17	13 / 100	3071 ms	8952 KiB

bridges

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int MAXN = (int)1e5 + 5;

int a[MAXN];
vector <pii> g[MAXN];
int edge[MAXN];

int used[MAXN], used_id = 1;

int get(int v, int x) {
	used_id++;
	queue <int> q;
	int ans = 0;
	q.push(v);
	used[v] = used_id;
	while (!q.empty()) {
		ans++;
		int vrt = q.front();
		q.pop();
		for (auto el : g[vrt]) {
			if (used[el.fr] != used_id && edge[el.sc] >= x) {
				used[el.fr] = used_id;
				q.push(el.fr);
			}
		}
	}
	return ans;
}

signed main() {
	fastInp;
	int n, m, q;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		edge[i] = val;
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	cin >> q;
	int type;
	int vertex, x;
	int pos, new_val;
	while (q--) { 
		cin >> type;
		if (type == 1) {
			cin >> pos >> new_val;
			edge[pos] = new_val;
		}
		else {
			cin >> vertex >> x;
			cout << get(vertex, x) << endl;
		}
	}
}

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