Submission #202568

#	Time	Username	Problem	Language	Result	Execution time	Memory
202568		wilwxk	Collapse (JOI18_collapse)	C++14	30 / 100	187 ms	32116 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+5;
int edges[MAXN][2];
map<pair<int, int>, int> mp;
vector<int> t, x, y, w, p;
vector<int> seg[MAXN*4];
int ans[MAXN];
int n, m, q;

class dsu {
private:
	vector<pair<int, int> > st[MAXN];
	int rep[MAXN];
	int repp[MAXN];
public:
	int cnt;
	void init() {
		for(int i = 0; i <= n; i++) rep[i] = i, repp[i] = 1;
		cnt = n;
	}
	int find(int x) {
		return rep[x] == x ? x : find(rep[x]);
	}
	void une(int a, int b) {
		// printf("une %d %d\n", a, b);
		int aa = find(a);
		int bb = find(b);
		st[a].push_back({aa, repp[aa]});
		st[b].push_back({bb, repp[bb]});
		a = aa, b = bb;
		if(a == b) return;
		cnt--;
		if(repp[a] > repp[b]) swap(a, b);
		rep[a] = b;
		if(repp[a] == repp[b]) repp[b]++;
	}
	void undo(int a, int b) {
		// printf("undo %d %d\n", a, b);
		auto aa = st[a].back(); st[a].pop_back();
		auto bb = st[b].back(); st[b].pop_back();
		a = aa.first; b = bb.first;
		if(a == b) return;
		cnt++;
		rep[a] = aa.first; repp[a] = aa.second;
		rep[b] = bb.first; repp[b] = bb.second;
	}
};
dsu graph;

void update(int sind, int l, int r, int ql, int qr, int val) {
	if(ql > r || qr < l) return;
	if(ql <= l && qr >= r) {
		seg[sind].push_back(val);
		return;
	}
	int m = (l+r)/2;
	int e = sind*2; int d = e+1;
	update(e, l, m, ql, qr, val);
	update(d, m+1, r, ql, qr, val);
}

void prepare() {
	for(int i = 0; i < m; i++) {
		int a = x[i], b = y[i];
		if(a > b) swap(a, b);
		if(a <= p[0] && b > p[0]) continue;
		if(!t[i]) {
			mp[{a, b}] = i;
			edges[i][0] = i+1;
		}
		else {
			int id = mp[{a, b}];
			edges[id][1] = i;
		}
	}
	for(int i = 0; i < m; i++) {
		if(!edges[i][0]) continue;
		if(!edges[i][1]) edges[i][1] = m+1;
		// printf("upd %d %d %d\n", edges[i][0], edges[i][1], i);
		update(1, 1, m+1, edges[i][0], edges[i][1], i);
	}
	graph.init();
}

void solve(int sind, int l, int r) {
	// printf("solve %d %d %d\n", sind, l, r);
	for(int id : seg[sind]) graph.une(x[id], y[id]);
	if(l != r) {
		int m = (l+r)/2;
		int e = sind*2; int d = e+1;
		solve(e, l, m);
		solve(d, m+1, r);
	}
	else {
		// printf("ans %d %d\n", sind, l);
		ans[l] = graph.cnt;
	}
	for(int i = seg[sind].size()-1; i >= 0; i--) {
		int id = seg[sind][i];
		graph.undo(x[id], y[id]);
	}
}

vector<int> simulateCollapse(
	int N,
	vector<int> T,
	vector<int> X,
	vector<int> Y,
	vector<int> W,
	vector<int> P
) {
	n = N;
	m = T.size();
	q = W.size();
	t = T;
	x = X;
	y = Y;
	w = W;
	p = P;
	
	prepare();
	solve(1, 1, m+1);
	// for(int i = 1; i <= m+1; i++) printf("%d ", ans[i]);

	vector<int> fans;
	for(int day : W) fans.push_back(ans[day+1]); 
	return fans;
}

/*
5 5 5 
0 0 1
0 0 2
0 3 4
1 0 2
1 3 4
0 2
1 2
2 2
3 2
4 2
*/

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