Submission #1173952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173952		stdfloat	Bridges (APIO19_bridges)	C++20	14 / 100	54 ms	4020 KiB

bridges

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

using ll = long long;

#define ff	first
#define ss	second
#define pii	pair<int, int>

vector<int> p, sz;

int fnd(int x) {
	return p[x] = (x == p[x] ? x : fnd(p[x]));
}

void uni(int x, int y) {
	x = fnd(x); y = fnd(y);

	if (x == y) return;

	p[y] = x;
	sz[x] += sz[y]; sz[y] = 0;
}

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

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

	vector<pair<int, pii>> E;
	for (int i = 1; i <= m; i++) {
		int u, v, d;
		cin >> u >> v >> d;
		
		E.push_back({d, {u, v}});
	}

	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int t;
		cin >> t;

		assert(t == 2);
	
		int s, w;
		cin >> s >> w;

		E.push_back({w, {-i, s}});
	}

	sort(E.begin(), E.end());
	reverse(E.begin(), E.end());

	p = sz = vector<int>(n + 1, 1);
	iota(p.begin() + 1, p.end(), 1);

	vector<int> ans(q + 1);
	for (auto [w, i] : E) {
		if (0 < i.ff) uni(i.ff, i.ss);
		else ans[-i.ff] = sz[fnd(i.ss)];
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

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