Submission #1075746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075746		vjudge1	Bridges (APIO19_bridges)	C++17	100 / 100	1221 ms	10340 KiB

bridges

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

tuple<int, int, int> E[100008], Q[100008];
bool mark[100008]; int answer[100008];

struct Disjoint_Set_Union {
	static const int N = 5e4;
	int par[N + 8], sz[N + 8];
	vector<pair<int*, int>> history;
	
	void init(int n) {
		iota(par, par + n + 1, 0);
		fill(sz + 1, sz + n + 1, 1);
		history.clear();
	}
	
	int find(int u) {return (u == par[u] ? u : find(par[u]));}
	
	void join(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return;
		if (sz[u] < sz[v]) swap(u, v);
		history.push_back({par + v, par[v]});
		history.push_back({sz + u, sz[u]});
		par[v] = u; sz[u] += sz[v];
	}
	void join(int E_id) {join(get<0>(E[E_id]), get<1>(E[E_id]));}
	
	int current_snapshot() {return history.size();}
	void rollback_to(int ver) {
		while (history.size() > ver) {
			*history.back().first = history.back().second;
			history.pop_back();
		}
	}
	
	int query(int u) {return sz[find(u)];}
} DSU;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, u, v, w; cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> u >> v >> w;
		E[i] = {u, v, w};
	}
	vector<pair<int, int>> unchanged; vector<tuple<int, int, int>> queried; vector<int> changed;
	int q, tq, type, id, Qid, nw, tu, tv, tw, cur; cin >> q; 
	int S = 1200;
	for (int i = 1; i <= q; i += S) {
		tq = min(S, q - i + 1); queried.clear(); unchanged.clear(); changed.clear(); DSU.init(n);
		for (int j = i; j < i + tq; ++j) {
			cin >> type >> u >> v;
			Q[j] = {type, u, v};
			if (type == 1) mark[u] = 1, changed.push_back(u);
			else queried.push_back({v, u, j});
		}
		for (int i = 1; i <= m; ++i) if (!mark[i]) unchanged.push_back({get<2>(E[i]), i});
		for (int id : changed) mark[id] = 0;
		sort(unchanged.begin(), unchanged.end());
		sort(queried.begin(), queried.end(), greater<tuple<int, int, int>>());
		for (tuple<int, int, int> query : queried) {
			tie(w, u, Qid) = query; 
			while (!unchanged.empty() && unchanged.back().first >= w) 
				DSU.join(unchanged.back().second), unchanged.pop_back();
			cur = DSU.current_snapshot();
			for (int j = Qid - 1; j >= i; --j) if (get<0>(Q[j]) == 1) {
				tie(type, id, nw) = Q[j]; tie(tu, tv, tw) = E[id];
				if (nw >= w && !mark[id]) DSU.join(tu, tv);
				mark[id] = 1;
			}
			for (int j = Qid + 1; j < i + tq; ++j) if (get<0>(Q[j]) == 1) {
				tie(type, id, nw) = Q[j]; tie(tu, tv, tw) = E[id];
				if (tw >= w && !mark[id]) DSU.join(tu, tv);
			}
			for (int id : changed) mark[id] = 0;
			answer[Qid] = DSU.query(u);
			DSU.rollback_to(cur);
		}
		for (int j = i; j < i + tq; ++j) if (get<0>(Q[j]) == 1) {
			tie(type, id, nw) = Q[j]; tie(u, v, w) = E[id];
			E[id] = {u, v, nw};
		}
	}
	for (int i = 1; i <= q; ++i) if (answer[i]) cout << answer[i] << '\n';
}

Compilation message (stderr)

bridges.cpp: In member function 'void Disjoint_Set_Union::rollback_to(int)':
bridges.cpp:33:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int*, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |   while (history.size() > ver) {
      |          ~~~~~~~~~~~~~~~^~~~~

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