Submission #866077

#	Time	Username	Problem	Language	Result	Execution time	Memory
866077		qthang2k11	Bridges (APIO19_bridges)	C++17	59 / 100	3031 ms	61184 KiB

bridges

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

const int N = 5e4 + 5, M = 1e5 + 5, Q = M, S = sqrt(M);

int n, m, q, u[M], v[M], w[M];
int par[N], num[N];
bool changed[M];

bool vs[N];

inline int find(int x) {
	if (par[x] != x)
		par[x] = find(par[x]);
	return par[x];
}

void join(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (num[x] < num[y])
		swap(x, y);
	num[x] += num[y];
	par[y] = x;
}

int t[Q], x[Q], y[Q], ans[Q];

vector<int> edges[Q], adj[N];

int dfs(int x) {
	vs[x] = true;
	int ans = num[x];
	for (int y: adj[x])
		if (!vs[y]) ans += dfs(y);
	return ans;
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> n >> m;
	for (int i = 1; i <= m; i++) 
		cin >> u[i] >> v[i] >> w[i];
	cin >> q;
	for (int i = 1; i <= q; i++)
		cin >> t[i] >> x[i] >> y[i];
	
	for (int L = 1; L <= q; L += S) {
		int R = min(q, L + S - 1);
		
		fill(num + 1, num + n + 1, 1);
		iota(par + 1, par + n + 1, 1);
		fill(changed + 1, changed + m + 1, 0);
		
		vector<int> ask, unchanged, upd;
		for (int i = L; i <= R; i++) {
			if (t[i] == 1) {
				changed[x[i]] = true;
				upd.emplace_back(i);
			} else ask.emplace_back(i);
		}
		for (int i = 1; i <= m; i++)
			if (!changed[i])
				unchanged.emplace_back(i);
		int ucsz = unchanged.size();
		
		for (int i = L; i <= R; i++) {
			if (t[i] == 1) w[x[i]] = y[i];
			else {
				for (int id: upd)
					if (w[x[id]] >= y[i])
						edges[i].emplace_back(x[id]);
			}
		}
		
		sort(ask.begin(), ask.end(), [&] (int a, int b) {
			return y[a] > y[b];
		});
		sort(unchanged.begin(), unchanged.end(), [&] (int a, int b) {
			return w[a] > w[b];
		});
		
		int p = -1;
		for (int id: ask) {
			while (p + 1 < ucsz && w[unchanged[p + 1]] >= y[id]) 
				++p, join(u[unchanged[p]], v[unchanged[p]]);
			for (int eid: edges[id]) {
				int x = find(u[eid]), y = find(v[eid]);
				adj[x].emplace_back(y);
				adj[y].emplace_back(x); 
			}
			ans[id] = dfs(find(x[id]));
			
			vs[find(x[id])] = false;
			for (int eid: edges[id]) {
				int x = find(u[eid]), y = find(v[eid]);
				adj[x].clear();
				adj[y].clear();
				vs[x] = vs[y] = false; 
			}
		}
	}
	
	for (int i = 1; i <= q; i++)
		if (t[i] == 2) cout << ans[i] << '\n';
	
	return 0;
}

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