oj.uz

Submission #380887

# Submission time Handle Problem Language Result Execution time Memory
380887 2021-03-23T13:43:24 Z qwerty234 Collapse (JOI18_collapse) C++14
60 / 100
 7203 ms 28816 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;
	// if (n > 5005 || c > 5005 || q > 5005)
	// 	return {};
	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]}];
	}
	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;
	while (true) {
		int l = curblock * blocksz, r = min(l + blocksz - 1, q - 1);
		vis.assign(m, 0); state.assign(m, 0);
		if (l >= q) break;
		// cout << l << " " << r << endl;
		for (int j = 0; 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();
			}
		}
		curblock++;
	}
	return ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 620 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 -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3556 KB Output is correct
2 Correct 45 ms 3556 KB Output is correct
3 Correct 717 ms 6240 KB Output is correct
4 Correct 48 ms 3560 KB Output is correct
5 Correct 599 ms 6756 KB Output is correct
6 Correct 107 ms 4064 KB Output is correct
7 Correct 1445 ms 15712 KB Output is correct
8 Correct 739 ms 11236 KB Output is correct
9 Correct 482 ms 11232 KB Output is correct
10 Correct 481 ms 11360 KB Output is correct
11 Correct 531 ms 11488 KB Output is correct
12 Correct 1183 ms 18540 KB Output is correct
13 Correct 2803 ms 22880 KB Output is correct
14 Correct 6188 ms 27104 KB Output is correct
15 Correct 4677 ms 26716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3556 KB Output is correct
2 Correct 46 ms 3684 KB Output is correct
3 Correct 47 ms 3560 KB Output is correct
4 Correct 46 ms 3560 KB Output is correct
5 Correct 58 ms 3556 KB Output is correct
6 Correct 126 ms 4140 KB Output is correct
7 Correct 1141 ms 12660 KB Output is correct
8 Correct 2229 ms 17172 KB Output is correct
9 Correct 502 ms 14420 KB Output is correct
10 Correct 581 ms 13408 KB Output is correct
11 Correct 4748 ms 28512 KB Output is correct
12 Correct 7004 ms 28780 KB Output is correct
13 Correct 5238 ms 28816 KB Output is correct
14 Correct 7203 ms 28688 KB Output is correct
15 Correct 4659 ms 28560 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 620 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 -