oj.uz

Submission #380877

# Submission time Handle Problem Language Result Execution time Memory
380877 2021-03-23T12:50:40 Z qwerty234 Collapse (JOI18_collapse) C++14
60 / 100
 6603 ms 31492 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 = -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;
		if (prv == qu[l].plan_day) {
			state[refer[prv]] ^= 1;
			prv--;
		}
		for (int j = prv + 1; j < qu[l].plan_day; j++) state[refer[j]] ^= 1;
		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 = qu[l].plan_day; 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 = qu[l].plan_day; 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 = qu[l].plan_day; 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 = qu[l].plan_day; 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 = qu[l].plan_day; j <= qu[r].plan_day; j++) state[refer[j]] ^= 1;
		prv = qu[r].plan_day;
		curblock++;
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 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 34 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3556 KB Output is correct
2 Correct 43 ms 3556 KB Output is correct
3 Correct 597 ms 6240 KB Output is correct
4 Correct 45 ms 3560 KB Output is correct
5 Correct 542 ms 6752 KB Output is correct
6 Correct 105 ms 4064 KB Output is correct
7 Correct 1358 ms 15612 KB Output is correct
8 Correct 666 ms 11360 KB Output is correct
9 Correct 460 ms 11360 KB Output is correct
10 Correct 458 ms 11344 KB Output is correct
11 Correct 517 ms 11616 KB Output is correct
12 Correct 1093 ms 18656 KB Output is correct
13 Correct 2614 ms 22752 KB Output is correct
14 Correct 6240 ms 26976 KB Output is correct
15 Correct 4331 ms 26512 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3556 KB Output is correct
2 Correct 43 ms 3556 KB Output is correct
3 Correct 44 ms 3560 KB Output is correct
4 Correct 45 ms 3560 KB Output is correct
5 Correct 56 ms 3556 KB Output is correct
6 Correct 110 ms 4064 KB Output is correct
7 Correct 1093 ms 12640 KB Output is correct
8 Correct 2195 ms 19268 KB Output is correct
9 Correct 499 ms 15328 KB Output is correct
10 Correct 553 ms 14432 KB Output is correct
11 Correct 4497 ms 31108 KB Output is correct
12 Correct 6603 ms 31432 KB Output is correct
13 Correct 4863 ms 31492 KB Output is correct
14 Correct 6597 ms 31484 KB Output is correct
15 Correct 4602 ms 31316 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 640 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 34 ms 620 KB Output isn't correct
6 Halted 0 ms 0 KB -