oj.uz

Submission #202568

# Submission time Handle Problem Language Result Execution time Memory
202568 2020-02-17T01:58:39 Z wilwxk Collapse (JOI18_collapse) C++14
30 / 100
 187 ms 32116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12408 KB Output is correct
2 Incorrect 14 ms 12280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15092 KB Output is correct
2 Correct 44 ms 15092 KB Output is correct
3 Correct 98 ms 23412 KB Output is correct
4 Correct 43 ms 15604 KB Output is correct
5 Correct 123 ms 24436 KB Output is correct
6 Correct 48 ms 16500 KB Output is correct
7 Correct 162 ms 30324 KB Output is correct
8 Correct 134 ms 26992 KB Output is correct
9 Correct 46 ms 16628 KB Output is correct
10 Correct 46 ms 16628 KB Output is correct
11 Correct 49 ms 17012 KB Output is correct
12 Correct 164 ms 29908 KB Output is correct
13 Correct 170 ms 30584 KB Output is correct
14 Correct 187 ms 32116 KB Output is correct
15 Correct 166 ms 31896 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15096 KB Output is correct
2 Incorrect 40 ms 15092 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12408 KB Output is correct
2 Incorrect 14 ms 12280 KB Output isn't correct
3 Halted 0 ms 0 KB -