Submission #1044785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044785		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	48 ms	4444 KiB

bridges

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "debug.h"
#else 
	#define debug(...) void(23)
#endif

constexpr int maxN = int(5E4) + 5;

struct DSU {
	std::vector<int> par, siz;
	DSU() : DSU(0) {}
	DSU(int n) { init(n); }
	void init(int n) {
		par.assign(n, 0);
		siz.assign(n, 1);
		std::iota(par.begin(), par.end(), 0);
	}
	int get(int x) {
		while(x != par[x]) {
			x = par[x] = par[par[x]];
		}
		return x;
	}
	bool unite(int a, int b) {
		a = get(a), b = get(b);
		if(a == b) {
			return false;
		} else if(siz[a] > siz[b]) {
			std::swap(a, b);
		}
		par[a] = b;
		siz[b] += siz[a];
		return true;
	}
	int size(int x) {
		return siz[get(x)];
	}
};

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

	int N, M, Q;
	std::cin >> N >> M;
	std::vector<int> A(M), B(M), C(M);
	for(int i = 0; i < M; ++i) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
	}

	std::cin >> Q;

	bool flag = true;
	#ifdef LOCAL
		flag = false;
	#endif
	if(N <= 1000 && M <= 1000 && Q <= 10000 && flag) {
		std::vector<int> ord(M);
		std::iota(ord.begin(), ord.end(), 0);
		DSU dsu;
		for(int i = 0; i < Q; ++i) {
			debug(i);
			int T;
			std::cin >> T;
			if(T == 1) {
				int j, R;
				std::cin >> j >> R;
				--j;
				C[j] = R;
			} else {
				int S, W;
				std::cin >> S >> W;
				--S;
				dsu.init(N);
				std::sort(ord.begin(), ord.end(), [&](int lhs, int rhs) {
					return C[lhs] < C[rhs];
				});
				debug("wtf");
				for(int j : ord) {
					if(C[j] >= W) {
						dsu.unite(A[j], B[j]);
					}
				}
				debug("wtf");
				std::cout << dsu.size(S) << '\n';
			}
		}
		return 0;
	}

	std::vector<int> ord(M);
	std::iota(ord.begin(), ord.end(), 0);
	std::sort(ord.begin(), ord.end(), [&](int lhs, int rhs) {
		return C[lhs] < C[rhs];
	});

	std::vector<int> ans(Q);
	std::vector<std::pair<int, int>> qq(Q);
	for(int i = 0; i < Q; ++i) {
		int T, S, W;
		std::cin >> T >> S >> W;
		--S;
		assert(T == 2);
		qq[i] = {W, S};
	}

	std::vector<int> qrd(Q);
	std::iota(qrd.begin(), qrd.end(), 0);
	std::sort(qrd.begin(), qrd.end(), [&](int lhs, int rhs) {
		return qq[lhs] > qq[rhs];
	});

	DSU dsu(N);
	int ptr = 0;
	for(int i : qrd) {
		while(ptr < M && C[ord[ptr]] >= qq[i].first) {
			dsu.unite(A[ord[ptr]], B[ord[ptr]]);
			ptr += 1;
		}
		ans[i] = dsu.size(qq[i].second);
	}

	for(int i = 0; i < Q; ++i) {
		std::cout << ans[i] << '\n';
	}

	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