Submission #1044856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044856		vjudge1	다리 (APIO19_bridges)	C++17	27 / 100	156 ms	8804 KiB

bridges

#include <bits/stdc++.h>

using i64 = long long;

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

constexpr int INF = int(1E9);
constexpr int maxN = int(5E4) + 5;

std::vector<int> adj[maxN];

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)];
	}
};

#define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
struct segtree {
	struct node {
		int val;
		node() : val(INF) {}
		node(int x) : val(x) {}
	};
	node unite(node lhs, node rhs) {
		return {std::min(lhs.val, rhs.val)};
	}
	int n;
	std::vector<node> tree;
	segtree(int _n) : n(_n), tree(n << 1) {}
	void modify(int v, int l, int r, int p, int x) {
		if(l == r) {
			tree[v] = {x};
			return;
		}
		def;
		if(p <= mid) {
			modify(v + 1, l, mid, p, x);
		} else {
			modify(rv, mid + 1, r, p, x);
		}
		tree[v] = unite(tree[v + 1], tree[rv]);
	}
	void modify(int p, int x) {
		assert(0 <= p && p < n);
		modify(0, 0, n - 1, p, x);
	}

	int query(int v, int l, int r, int ql, int qr) {
		if(ql <= l && r <= qr) {
			return tree[v].val;
		}
		def;
		if(qr <= mid) {
			return query(v + 1, l, mid, ql, qr);
		} else if(mid + 1 <= ql) {
			return query(rv, mid + 1, r, ql, qr);
		}
		return std::min(query(v + 1, l, mid, ql, qr), 
						query(rv, mid + 1, r, ql, qr));
	}
	int query(int l, int r) {
		if(l > r) {
			return INF;
		}
		return query(0, 0, n - 1, l, r);
	}
};

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), t(N);
	for(int i = 0; i < M; ++i) {
		std::cin >> A[i] >> B[i] >> C[i];
		--A[i], --B[i];
		t[A[i]] += 1;
		t[B[i]] += 1;
		adj[A[i]].emplace_back(i);
		adj[B[i]].emplace_back(i);
	}

	std::cin >> Q;
	bool good = true;
	int cnt = 0;
	for(int i = 0; i < N; ++i) {
		good &= t[i] <= 2;
		cnt += t[i] == 1;
	}

	good &= cnt == 2;

	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;
	} else if(good) {
		int root = 0;
		while(adj[root].size() == 2) {
			root += 1;
		}

		debug(root);

		int cur = root, par = root, timer = 0, timernode = 0;
		std::vector<int> gone, taken(N), timen(N);
		do {
			timen[cur] = timernode++;
			for(int i : adj[cur]) {
				int u = A[i] ^ B[i] ^ cur;
				if(u != par) {
					taken[i] = timer++;
					gone.emplace_back(i);
					par = cur;
					cur = u;
					break;
				}
			}
			debug(cur, par);
		} while(adj[cur].size() == 2);
		timen[cur] = timernode++;

		debug(gone, taken, timen);

		segtree seg(N - 1);
		for(int i = 0; i < N - 1; ++i) {
			seg.modify(taken[i], C[i]);
		}
		for(int _ = 0; _ < Q; ++_) {
			int T;
			std::cin >> T;
			if(T == 1) {
				int i, r;
				std::cin >> i >> r;
				--i;
				seg.modify(taken[i], r);
			} else {
				int S, W;
				std::cin >> S >> W;
				--S;
				int L, R;
				{
					int lo = 0, hi = timen[S];
					while(lo < hi) {
						int mid = (lo + hi) >> 1;
						if(W <= seg.query(lo, hi - 1)) {
							hi = mid;
						} else {
							lo = mid + 1;
						}
					}
					L = lo;
				}
				{
					int lo = timen[S], hi = N - 1;
					while(lo < hi) {
						int mid = (lo + hi + 1) >> 1;
						if(W <= seg.query(lo, hi - 1)) {
							lo = mid;
						} else {
							hi = mid -1;
						}
					}
					R = lo;
				}
				debug(L, R);
				std::cout << R - L + 1 << '\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: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27