oj.uz

Submission #761135

# Submission time Handle Problem Language Result Execution time Memory
761135 2023-06-19T09:03:36 Z SanguineChameleon Parachute rings (IOI12_rings) C++17
100 / 100
 681 ms 71168 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 20;
vector<pair<int, int>> edges;
int deg[4][maxn];
int L[4][maxn];
int R[4][maxn];
int len[maxn];
int cand[4];
bool good[4];
int n;
int cycle;

void Init(int _n) {
	n = _n;
	for (int k = 0; k < 4; k++) {
		cand[k] = -1;
	}
	for (int i = 0; i < n; i++) {
		L[0][i] = i;
		R[0][i] = i;
		len[i] = 1;
	}
}

void update(int k, int u, int v) {
	if (!good[k]) {
		return;
	}
	if (u == cand[k] || v == cand[k]) {
		return;
	}
	if (deg[k][u] == 2 || deg[k][v] == 2) {
		good[k] = false;
		return;
	}
	deg[k][u]++;
	deg[k][v]++;
	int lu = L[k][u];
	int ru = R[k][u];
	int lv = L[k][v];
	int rv = R[k][v];
	if (lu == lv) {
		good[k] = false;
		return;
	}
	if (lu == u) {
		swap(lu, ru);
		L[k][lu] = lu;
		L[k][ru] = lu;
		R[k][lu] = ru;
		R[k][ru] = ru;
	}
	if (rv == v) {
		swap(lv, rv);
		L[k][lv] = lv;
		L[k][rv] = lv;
		R[k][lv] = rv;
		R[k][rv] = rv;
	}
	L[k][lu] = lu;
	R[k][lu] = rv;
	L[k][rv] = lu;
	R[k][rv] = rv;
}

void Link(int u, int v) {
	if (cand[0] == -1) {
		edges.emplace_back(u, v);
		deg[0][u]++;
		deg[0][v]++;
		if (deg[0][v] == 3) {
			swap(u, v);
		}
		if (deg[0][u] == 3) {
			cand[0] = u;
			int cnt = 0;
			for (auto e: edges) {
				if (e.first == u) {
					cand[++cnt] = e.second;
				}
				else if (e.second == u) {
					cand[++cnt] = e.first;
				}
			}
			for (int k = 0; k < 4; k++) {
				good[k] = true;
				for (int i = 0; i < n; i++) {
					deg[k][i] = 0;
					L[k][i] = i;
					R[k][i] = i;
				}
			}
			for (auto e: edges) {
				for (int k = 0; k < 4; k++) {
					update(k, e.first, e.second);
				}
			}
			edges.clear();
		}
		else {
			int len_u = len[u];
			int len_v = len[v];
			int lu = L[0][u];
			int ru = R[0][u];
			int lv = L[0][v];
			int rv = R[0][v];
			if (lu == lv) {
				if (cycle == 0) {
					cycle = len_u;
				}
				else {
					cycle = -1;
				}
				return;
			}
			if (lu == u) {
				swap(lu, ru);
				L[0][lu] = lu;
				L[0][ru] = lu;
				R[0][lu] = ru;
				R[0][ru] = ru;
			}
			if (rv == v) {
				swap(lv, rv);
				L[0][lv] = lv;
				L[0][rv] = lv;
				R[0][lv] = rv;
				R[0][rv] = rv;
			}
			L[0][lu] = lu;
			R[0][lu] = rv;
			L[0][rv] = lu;
			R[0][rv] = rv;
			len[lu] = len_u + len_v;
			len[rv] = len_u + len_v;
		}
	}
	else {
		for (int k = 0; k < 4; k++) {
			update(k, u, v);
		}
	}
}

int CountCritical() {
	if (cand[0] == -1) {
		if (cycle == 0) {
			return n;
		}
		else if (cycle == -1) {
			return 0;
		}
		else {
			return cycle;
		}
	}
	else {
		return good[0] + good[1] + good[2] + good[3];
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12700 KB Output is correct
2 Correct 312 ms 43308 KB Output is correct
3 Correct 156 ms 51220 KB Output is correct
4 Correct 302 ms 24384 KB Output is correct
5 Correct 353 ms 37348 KB Output is correct
6 Correct 303 ms 36528 KB Output is correct
7 Correct 157 ms 63520 KB Output is correct
8 Correct 570 ms 65644 KB Output is correct
9 Correct 681 ms 71168 KB Output is correct
10 Correct 256 ms 36140 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 2 ms 980 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 980 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 3 ms 1236 KB Output is correct
13 Correct 3 ms 1108 KB Output is correct
14 Correct 2 ms 980 KB Output is correct
15 Correct 2 ms 1492 KB Output is correct
16 Correct 2 ms 852 KB Output is correct
17 Correct 2 ms 980 KB Output is correct
18 Correct 2 ms 1492 KB Output is correct
19 Correct 2 ms 852 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 9 ms 2008 KB Output is correct
22 Correct 14 ms 3024 KB Output is correct
23 Correct 18 ms 3544 KB Output is correct
24 Correct 18 ms 5944 KB Output is correct
25 Correct 10 ms 5844 KB Output is correct
26 Correct 18 ms 6244 KB Output is correct
27 Correct 23 ms 3984 KB Output is correct
28 Correct 21 ms 6044 KB Output is correct
29 Correct 18 ms 6272 KB Output is correct
30 Correct 18 ms 4016 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 528 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 108 ms 12700 KB Output is correct
12 Correct 312 ms 43308 KB Output is correct
13 Correct 156 ms 51220 KB Output is correct
14 Correct 302 ms 24384 KB Output is correct
15 Correct 353 ms 37348 KB Output is correct
16 Correct 303 ms 36528 KB Output is correct
17 Correct 157 ms 63520 KB Output is correct
18 Correct 570 ms 65644 KB Output is correct
19 Correct 681 ms 71168 KB Output is correct
20 Correct 256 ms 36140 KB Output is correct
21 Correct 1 ms 724 KB Output is correct
22 Correct 3 ms 1236 KB Output is correct
23 Correct 3 ms 1108 KB Output is correct
24 Correct 2 ms 980 KB Output is correct
25 Correct 2 ms 1492 KB Output is correct
26 Correct 2 ms 852 KB Output is correct
27 Correct 2 ms 980 KB Output is correct
28 Correct 2 ms 1492 KB Output is correct
29 Correct 2 ms 852 KB Output is correct
30 Correct 3 ms 1236 KB Output is correct
31 Correct 9 ms 2008 KB Output is correct
32 Correct 14 ms 3024 KB Output is correct
33 Correct 18 ms 3544 KB Output is correct
34 Correct 18 ms 5944 KB Output is correct
35 Correct 10 ms 5844 KB Output is correct
36 Correct 18 ms 6244 KB Output is correct
37 Correct 23 ms 3984 KB Output is correct
38 Correct 21 ms 6044 KB Output is correct
39 Correct 18 ms 6272 KB Output is correct
40 Correct 18 ms 4016 KB Output is correct
41 Correct 96 ms 15592 KB Output is correct
42 Correct 327 ms 54744 KB Output is correct
43 Correct 170 ms 52512 KB Output is correct
44 Correct 159 ms 59596 KB Output is correct
45 Correct 304 ms 60684 KB Output is correct
46 Correct 256 ms 32328 KB Output is correct
47 Correct 318 ms 32852 KB Output is correct
48 Correct 186 ms 59212 KB Output is correct
49 Correct 268 ms 34348 KB Output is correct
50 Correct 269 ms 33720 KB Output is correct
51 Correct 159 ms 45612 KB Output is correct
52 Correct 164 ms 48628 KB Output is correct
53 Correct 161 ms 58448 KB Output is correct
54 Correct 477 ms 56468 KB Output is correct
55 Correct 251 ms 57520 KB Output is correct