Submission #1261821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261821		Bui_Quoc_Cuong	Collapse (JOI18_collapse)	C++20	5 / 100	1500 ms	25664 KiB

collapse

#include <bits/stdc++.h>
// #include "collapse.h"
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define all(a) a.begin(), a.end()
#define pb push_back
#define fi first
#define se second
const int maxN = 1e5 + 5;

int n, m, q;
array <int, 3> edges[maxN];
array <int, 2> Q[maxN];

void init() {
	cin >> n >> m >> q;
	FOR(i, 1, m) {
		cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
		edges[i][1]++; edges[i][2]++;
		if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
	}
	FOR(i, 1, q) {
		cin >> Q[i][0] >> Q[i][1];
		Q[i][0]++; Q[i][1]++;
	}
}

namespace sub1 {
	bool checksub() {
		return max(n, q) <= 5000;
	}	

	set <int> G[5005];
	bool vis[5005];

	void dfs(int u, int p) {
		if (vis[u]) return;
		vis[u] = 1;
		for(auto v : G[u]) if (v != p && vis[v] == 0) {
			dfs(v, u);
		}
	}

	vector <int> solve() {
		vector <int> res;
		FOR(_q, 1, q) {
			FOR(i, 1, n) G[i].clear();
			int ssc = 0;

			FOR(i, 1, Q[_q][0]) {
				if (edges[i][0] == 1) {
					int u = edges[i][1], v = edges[i][2];
					if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
					G[u].erase(v);
					G[v].erase(u);	 
				} else {
					int u = edges[i][1], v = edges[i][2];
					if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
					G[u].insert(v);
					G[v].insert(u);
				}
			}

			FOR(i, 1, n) vis[i] = 0;
			FOR(i, 1, n) if (!vis[i]) {
				ssc++;
				dfs(i, i);
			}

			res.push_back(ssc);
		}
		return res;
	}	
}

struct DisjointSet{
	struct Data {
		int u, lu, v, lv, ssc;
	}; stack <Data> memo;
	int ssc, lab[maxN];

	int find(int x) {
		return lab[x] < 0 ? x : find(lab[x]);
	}

	bool joint(int u, int v) {
		int x = find(u), y = find(v);
		if (x == y) return false;
		if (lab[x] > lab[y]) swap(x, y);
		memo.push({x, lab[x], y, lab[y], ssc});
		lab[x]+= lab[y];
		lab[y] = x;
		ssc--;
		return true;
	}

	int get_version() {
		return (int)memo.size();
	}

	void rollback(int vers) {
		while ((int)memo.size() > vers) {
			lab[memo.top().u] = memo.top().lu;
			lab[memo.top().v] = memo.top().lv;
			ssc = memo.top().ssc;
			memo.pop();
		}
	}
} DSU;

namespace sub2 {
	bool checksub() {
		FOR(i, 1, q) if (Q[i][1] != Q[1][1]) return 0;
		return 1;
	}
	
	vector <pair <int, int>> st[4 * maxN];
	vector <int> ask[maxN];
	int ans[maxN], far_query[maxN];
	map <pair <int, int>, int> last;

	void update(int id, int l, int r, int u, int v, int id_edge) {
		if (l > v || r < u) return;
		if (l >= u && r <= v) {
			st[id].push_back(make_pair(edges[id_edge][1], edges[id_edge][2]));
			return;
		}
		int mid = (l + r) >> 1;
		update (id << 1, l, mid, u, v, id_edge);
		update (id << 1 | 1, mid + 1, r, u, v, id_edge);
	}

	void go(int id, int l, int r) {
		int vers = DSU.get_version();
		for (auto &e : st[id]) DSU.joint(e.first, e.second);
		if (l == r) {
			for (auto &id : ask[l]) {
				ans[id] = DSU.ssc;
			}
			DSU.rollback(vers);
			return;
		}
		int mid = (l + r) >> 1;
		go (id << 1, l, mid);
		go (id << 1 | 1, mid + 1, r);
		DSU.rollback(vers);
	}

	vector <int> solve() {
		int border = Q[1][1];
		FOR(i, 1, m) {
			if (edges[i][1] <= border && edges[i][2] > border) continue;
			if (edges[i][0] == 0) {
				far_query[i] = m;	
				last[make_pair(edges[i][1], edges[i][2])] = i;	
			} else {
				far_query[last[make_pair(edges[i][1], edges[i][2])]] = i - 1;
			}
		}
		FOR(i, 1, m) if (edges[i][0] == 0) {
			update(1, 1, m, i, far_query[i], i);
		}
		FOR(i, 1, q) ask[Q[i][0]].push_back(i);
		FOR(i, 1, n) DSU.lab[i] = - 1;
		DSU.ssc = n;
		go(1, 1, m);
		vector <int> res;
		FOR(i, 1, q) res.push_back(ans[i]);
		FOR(i, 1, q) cout << ans[i] << " ";
		return res;
	}
}

namespace sub3 {
	int ans[maxN];
	set <pair <int, int>> out_block, in_block;
	vector <pair <int, int>> eblock[maxN];
	vector <int> ask[maxN], askp[maxN];
	vector <int> g[maxN];

	void solve() {
		FOR(i, 1, q) ask[Q[i][0]].push_back(i);
		for (int i = 1; i <= m; i+= 320) {
			int L = i, R = min(m, i + 320 - 1);
			in_block.clear();

			FOR(j, 1, n) askp[j].clear();

			FOR(j, L, R) {
				int u = edges[j][1], v = edges[j][2];
				if (out_block.find(make_pair(u, v)) != out_block.end()) {
					out_block.erase(make_pair(u, v));
					in_block.insert(make_pair(u, v));
				}
				for (auto id : ask[j]) askp[Q[id][1]].push_back(id);
			}

			FOR(j, L, R) {
				int u = edges[j][1], v = edges[j][2];
				if (edges[j][0] == 0) {
					in_block.insert(make_pair(u, v));
				} else in_block.erase(make_pair(u, v));
				for (auto it : in_block) eblock[j].push_back(it);
			}

			FOR(j, 1, n) {
				DSU.lab[j] = - 1;
				g[j].clear();
				DSU.ssc = n;
			}
			while (!DSU.memo.empty()) DSU.memo.pop();
			for (auto x : out_block) g[x.se].push_back(x.fi);

			FOR(j, 1, n) {
				for (auto x : g[j]) DSU.joint(x, j);
				int vers = DSU.get_version();
				for (auto id : askp[j]) {
					for (auto x : eblock[Q[id][0]]) {
						if (max(x.first, x.second) <= j) DSU.joint(x.first, x.second);
					}
					ans[id]+= DSU.ssc;
					DSU.rollback(vers);
				}
			}

			FOR(j, 1, n) {
				DSU.lab[j] = - 1;
				g[j].clear();
				DSU.ssc = n;
			}
			while (!DSU.memo.empty()) DSU.memo.pop();
			for (auto x : out_block) g[x.fi].push_back(x.se);

			FORD(j, n, 1) {
				int vers = DSU.get_version();
				for (auto id : askp[j]) {
					for (auto x : eblock[Q[id][0]]) {
						if (min(x.first, x.second) > j) DSU.joint(x.first, x.second);
					}
					ans[id]+= DSU.ssc;
					DSU.rollback(vers);
				}
				for (auto x : g[j]) DSU.joint(x, j);
			}

			for (auto x : in_block) out_block.insert(x);
		}	

		FOR(i, 1, q) cout << ans[i] - n << " ";
	}
}

vector <int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
	n = N;
	m = X.size();
	q = W.size();
	FOR(i, 0, m - 1) {
		edges[i + 1][0] = T[i];
		edges[i + 1][1] = X[i] + 1;
		edges[i + 1][2] = Y[i] + 1;
		if (edges[i + 1][1] > edges[i + 1][2]) swap(edges[i + 1][1], edges[i + 1][2]);
	}
	for (int i = 0; i < q; i++) {
		Q[i + 1][0] = W[i] + 1;
		Q[i + 1][1] = P[i] + 1;
	}	
	vector <int> res;
	if (sub1::checksub()) res = sub1::solve();
	else if (sub2::checksub()) res = sub2::solve(); 
	return res;
}

void process() {
	vector <int> res;
	// if (sub1::checksub()) res = sub1::solve();
	// for (int &val : res) cout << val << " ";
	// cout << "\n";
	// if (sub2::checksub()) res = sub2::solve();	
	// for (int &val : res) cout << val << " ";
	// cout << "\n";
	sub3::solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35