oj.uz

Submission #380881

# Submission time Handle Problem Language Result Execution time Memory
380881 2021-03-23T13:13:54 Z qwerty234 Collapse (JOI18_collapse) C++14
60 / 100
 6769 ms 29200 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;
	// cout << (0 ^ 1) << " " << (1 ^ 1) << 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 < m; i++) state[i] = 0;
		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;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:72:20: warning: unused variable 'prv' [-Wunused-variable]
   72 |  int curblock = 0, prv = -1;
      |                    ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 708 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 3576 KB Output is correct
3 Correct 656 ms 6240 KB Output is correct
4 Correct 44 ms 3560 KB Output is correct
5 Correct 597 ms 6752 KB Output is correct
6 Correct 111 ms 4192 KB Output is correct
7 Correct 1477 ms 15556 KB Output is correct
8 Correct 737 ms 11616 KB Output is correct
9 Correct 461 ms 11360 KB Output is correct
10 Correct 471 ms 11252 KB Output is correct
11 Correct 518 ms 11744 KB Output is correct
12 Correct 1163 ms 18640 KB Output is correct
13 Correct 2713 ms 22752 KB Output is correct
14 Correct 6257 ms 27136 KB Output is correct
15 Correct 4453 ms 26976 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 3556 KB Output is correct
2 Correct 44 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 57 ms 3556 KB Output is correct
6 Correct 115 ms 4064 KB Output is correct
7 Correct 1154 ms 12696 KB Output is correct
8 Correct 2228 ms 16992 KB Output is correct
9 Correct 476 ms 14560 KB Output is correct
10 Correct 562 ms 13536 KB Output is correct
11 Correct 4584 ms 28704 KB Output is correct
12 Correct 6769 ms 28944 KB Output is correct
13 Correct 4760 ms 28848 KB Output is correct
14 Correct 6509 ms 29200 KB Output is correct
15 Correct 4710 ms 28836 KB Output is correct

Subtask #4
0 / 35.0

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