답안 #380875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380875 2021-03-23T12:46:31 Z qwerty234 Collapse (JOI18_collapse) C++14
30 / 100
6458 ms 27176 KB
#include <bits/stdc++.h>
#include "collapse.h"
#define pb push_back
#define fi first
#define se second
using namespace std;

const int blocksz = 300;

struct query {
	int plan_day, collapse_town, id;
	query(int x, int y, int z) {plan_day = x; collapse_town = y; id = z;}
};
bool cmpquery(query A, query B) {return A.plan_day < B.plan_day;}

struct operation {
	int u, v, sz_u, sz_v;
	operation(int x, int y, int z, int d) {u = x; v = y; sz_u = z; sz_v = d;}
};
vector <int> sz, p;
vector <operation> op;
int sz_comp;

void make_set(int n) {
	sz.assign(n, 1); p.assign(n, 0); op.clear();
	for (int i = 0; i < n; i++) p[i] = i;
	sz_comp = n;
}

int getp(int u) {
	if (p[u] == u) return u;
	return getp(p[u]);
}

int add(int u, int v) {
	u = getp(u); v = getp(v);
	if (u == v) return 0;
	if (sz[u] > sz[v]) swap(u, v);
	op.pb({u, v, sz[u], sz[v]});
	p[u] = v;
	sz[v] += sz[u];
	sz_comp--;
	return 1;
}

void go_back() {
	operation opp = op[op.size() - 1];
	int u = opp.u, v = opp.v, sz_u = opp.sz_u, sz_v = opp.sz_v;
	p[u] = u; p[v] = v; sz[u] = sz_u; sz[v] = sz_v;
	sz_comp++;
	op.pop_back();
}

vector <int> simulateCollapse(int n, vector <int> t, vector <int> x, vector <int> y, vector <int> w, vector <int> p) {
	int c = t.size(), q = w.size(), m = 0;
	vector <query> qu; qu.clear();
	for (int i = 0; i < q; i++) {
		qu.pb({w[i], p[i], i});
	}
	sort(qu.begin(), qu.end(), cmpquery);
	vector <int> refer, state, vis; refer.assign(c, 0);
	vector <pair<int, int>> edges; edges.clear();
	map <pair<int, int>, int> edge_id; edge_id.clear();
	for (int i = 0; i < c; i++) {
		if (x[i] > y[i]) swap(x[i], y[i]);
		if (!edge_id.count({x[i], y[i]})) edge_id[{x[i], y[i]}] = m++, edges.pb({x[i], y[i]});
		refer[i] = edge_id[{x[i], y[i]}];
	}
	state.assign(m, 0);
	vector <vector<int>> min_v, max_v, qus_v; min_v.assign(n, {}); max_v.assign(n, {}); qus_v.assign(n, {});
	vector <int> ans; ans.assign(q, 0);
	int curblock = 0, prv;
	prv = qu[0].plan_day - 1;
	for (int j = 0; j <= prv; j++) state[refer[j]] ^= 1;
	// for (int i = 0; i < m; i++) {
	// 	cout << i << " " << edges[i].fi << " " << edges[i].se << endl;
	// }
	// for (int i = 0; i < c; i++) {
	// 	cout << t[i] << " " << x[i] << " " << y[i] << " " << refer[i] << endl;
	// }
	// for (int i = 0; i < q; i++)
	// 	cout << qu[i].plan_day << " " << qu[i].collapse_town << " " << qu[i].id << endl;
	// cout << endl;

	while (true) {
		int l = curblock * blocksz, r = min(l + blocksz - 1, q - 1);
		vis.assign(m, 0);
		if (l >= q) break;
		for (int i = 0; i < n; i++) min_v[i].clear(), max_v[i].clear(), qus_v[i].clear();
		for (int i = l; i <= r; i++) {
			vis[refer[qu[i].plan_day]] = 1;
			qus_v[qu[i].collapse_town].pb(i);
		}
		for (int i = 0; i < m; i++) {
			if (state[i] && !vis[i]) {
				min_v[edges[i].fi].pb(i);
				max_v[edges[i].se].pb(i);
			}
		}
		make_set(n);
		for (int i = 0; i <= n - 2; i++) {
			for (int id : max_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i]) {
				int cnt_op = 0;
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && edges[refer[j]].se <= i)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - (n - i - 1);
				// cout << "left " << qu[id].id << " " << sz_comp - (n - i - 1) << endl;
				while (cnt_op--) go_back();
			}
		}
		make_set(n);
		for (int i = n - 1; i >= 1; i--) {
			for (int id : min_v[i])
				add(edges[id].fi, edges[id].se);
			for (int id : qus_v[i - 1]) {
				int cnt_op = 0;
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				for (int j = qu[l].plan_day; j <= qu[r].plan_day; j++) {
					if (state[refer[j]] && i <= edges[refer[j]].fi)
						cnt_op += add(edges[refer[j]].fi, edges[refer[j]].se);
				}
				for (int j = prv + 1; j <= qu[id].plan_day; j++) state[refer[j]] ^= 1;
				ans[qu[id].id] += sz_comp - i;
				// cout << "rt " << qu[id].id << " " << sz_comp - i << endl;
				while (cnt_op--) go_back();
			}
		}
		for (int j = prv + 1; j <= qu[r].plan_day; j++) state[refer[j]] ^= 1;
		prv = qu[r].plan_day;
		curblock++;
	}
	return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Incorrect 33 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 3556 KB Output is correct
2 Correct 43 ms 3684 KB Output is correct
3 Correct 651 ms 6240 KB Output is correct
4 Correct 43 ms 3560 KB Output is correct
5 Correct 557 ms 6752 KB Output is correct
6 Correct 101 ms 4064 KB Output is correct
7 Correct 1376 ms 15584 KB Output is correct
8 Correct 669 ms 11360 KB Output is correct
9 Correct 520 ms 11360 KB Output is correct
10 Correct 473 ms 11344 KB Output is correct
11 Correct 521 ms 11616 KB Output is correct
12 Correct 1107 ms 18684 KB Output is correct
13 Correct 2727 ms 22724 KB Output is correct
14 Correct 6458 ms 27176 KB Output is correct
15 Correct 4613 ms 26620 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 3576 KB Output is correct
2 Correct 42 ms 3556 KB Output is correct
3 Correct 44 ms 3560 KB Output is correct
4 Correct 50 ms 3560 KB Output is correct
5 Correct 56 ms 3556 KB Output is correct
6 Correct 141 ms 4064 KB Output is correct
7 Incorrect 1088 ms 12616 KB Output isn't correct
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 748 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 3 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Incorrect 33 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -