oj.uz

Submission #415917

# Submission time Handle Problem Language Result Execution time Memory
415917 2021-06-01T17:23:25 Z arayi Parachute rings (IOI12_rings) C++17
100 / 100
 2606 ms 115264 KB 
#include <cassert>
#include <vector>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
using namespace std;

const int N = 1e6 + 30;
vector<int> g[N], fp;
vector<pair<int, int> > m;
int p[N], sz[N], col[N], v[4][N], pr[4][N];
int n, mx, ans;

int gp(int x)
{
	if (p[x] == x) return x;
	return p[x] = gp(p[x]);
}
int gp(int i1, int x)
{
	if (pr[i1][x] == x) return x;
	return pr[i1][x] = gp(i1, pr[i1][x]);
}
void edge(int a, int b, int i1)
{
	if (a == fp[i1] || b == fp[i1]) return;
	v[i1][a]++, v[i1][b]++;
	if (gp(i1, a) == gp(i1, b) || v[i1][a] > 2 || v[i1][b] > 2) col[i1] = 1;
	pr[i1][gp(i1, b)] = gp(i1, a);
}
void Init(int N_) 
{
	n = N_;
	for (int i = 1; i <= n; i++)
	{
		p[i] = i, sz[i] = 1;
		for (int j = 0; j < 4; j++) pr[j][i] = i;
	}
}

void Link(int A, int B) 
{
	A++, B++;
	g[A].ad(B);
	g[B].ad(A);
	m.ad(MP(A, B));
	if (mx <= 2)
	{
		mx = max(mx, max((int)g[A].size(), (int)g[B].size()));
		if (g[B].size() > g[A].size()) swap(A, B);
		if (mx >= 3)
		{
			fp.ad(A);
			for (auto p : g[A]) fp.ad(p);
			assert((int)fp.size() == 4);
			for (auto p : m) 
				for (int i = 0; i < 4; i++)
					edge(p.fr, p.sc, i);
			return;
		}
		if (gp(A) == gp(B))
		{
			if (ans == 0) ans = sz[gp(A)];
			else ans = -1;
		}
		else
		{
			sz[gp(A)] += sz[gp(B)];
			p[gp(B)] = gp(A);
		}
	}
	else
		for (int i = 0; i < 4; i++)
			edge(A, B, i);
}

int CountCritical() 
{
	if (mx <= 2)
	{
		if (ans == -1) return 0;
		else if (ans == 0) return n;
		else return ans;
	}
	else
	{
		int ret = 0;
		for (int i = 0; i < 4; i++) if (!col[i]) ret++;
		return ret;
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 23 ms 24196 KB Output is correct
3 Correct 21 ms 24252 KB Output is correct
4 Correct 18 ms 23848 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 18 ms 24056 KB Output is correct
9 Correct 19 ms 24236 KB Output is correct
10 Correct 19 ms 24372 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 63252 KB Output is correct
2 Correct 1533 ms 97036 KB Output is correct
3 Correct 2406 ms 110176 KB Output is correct
4 Correct 1291 ms 99736 KB Output is correct
5 Correct 1382 ms 99728 KB Output is correct
6 Correct 1262 ms 97984 KB Output is correct
7 Correct 2194 ms 108792 KB Output is correct
8 Correct 1746 ms 109444 KB Output is correct
9 Correct 2606 ms 115264 KB Output is correct
10 Correct 891 ms 96780 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 23 ms 24196 KB Output is correct
3 Correct 21 ms 24252 KB Output is correct
4 Correct 18 ms 23848 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 18 ms 24056 KB Output is correct
9 Correct 19 ms 24236 KB Output is correct
10 Correct 19 ms 24372 KB Output is correct
11 Correct 21 ms 24328 KB Output is correct
12 Correct 25 ms 24712 KB Output is correct
13 Correct 23 ms 24780 KB Output is correct
14 Correct 20 ms 24480 KB Output is correct
15 Correct 21 ms 24908 KB Output is correct
16 Correct 20 ms 24524 KB Output is correct
17 Correct 24 ms 24760 KB Output is correct
18 Correct 26 ms 25284 KB Output is correct
19 Correct 24 ms 24536 KB Output is correct
20 Correct 25 ms 24760 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 23 ms 24196 KB Output is correct
3 Correct 21 ms 24252 KB Output is correct
4 Correct 18 ms 23848 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 18 ms 24056 KB Output is correct
9 Correct 19 ms 24236 KB Output is correct
10 Correct 19 ms 24372 KB Output is correct
11 Correct 21 ms 24328 KB Output is correct
12 Correct 25 ms 24712 KB Output is correct
13 Correct 23 ms 24780 KB Output is correct
14 Correct 20 ms 24480 KB Output is correct
15 Correct 21 ms 24908 KB Output is correct
16 Correct 20 ms 24524 KB Output is correct
17 Correct 24 ms 24760 KB Output is correct
18 Correct 26 ms 25284 KB Output is correct
19 Correct 24 ms 24536 KB Output is correct
20 Correct 25 ms 24760 KB Output is correct
21 Correct 41 ms 26548 KB Output is correct
22 Correct 65 ms 28180 KB Output is correct
23 Correct 74 ms 29320 KB Output is correct
24 Correct 84 ms 30152 KB Output is correct
25 Correct 38 ms 28248 KB Output is correct
26 Correct 77 ms 31052 KB Output is correct
27 Correct 65 ms 30136 KB Output is correct
28 Correct 101 ms 31760 KB Output is correct
29 Correct 64 ms 30112 KB Output is correct
30 Correct 85 ms 31088 KB Output is correct

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23756 KB Output is correct
2 Correct 23 ms 24196 KB Output is correct
3 Correct 21 ms 24252 KB Output is correct
4 Correct 18 ms 23848 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 22 ms 24140 KB Output is correct
7 Correct 17 ms 24012 KB Output is correct
8 Correct 18 ms 24056 KB Output is correct
9 Correct 19 ms 24236 KB Output is correct
10 Correct 19 ms 24372 KB Output is correct
11 Correct 593 ms 63252 KB Output is correct
12 Correct 1533 ms 97036 KB Output is correct
13 Correct 2406 ms 110176 KB Output is correct
14 Correct 1291 ms 99736 KB Output is correct
15 Correct 1382 ms 99728 KB Output is correct
16 Correct 1262 ms 97984 KB Output is correct
17 Correct 2194 ms 108792 KB Output is correct
18 Correct 1746 ms 109444 KB Output is correct
19 Correct 2606 ms 115264 KB Output is correct
20 Correct 891 ms 96780 KB Output is correct
21 Correct 21 ms 24328 KB Output is correct
22 Correct 25 ms 24712 KB Output is correct
23 Correct 23 ms 24780 KB Output is correct
24 Correct 20 ms 24480 KB Output is correct
25 Correct 21 ms 24908 KB Output is correct
26 Correct 20 ms 24524 KB Output is correct
27 Correct 24 ms 24760 KB Output is correct
28 Correct 26 ms 25284 KB Output is correct
29 Correct 24 ms 24536 KB Output is correct
30 Correct 25 ms 24760 KB Output is correct
31 Correct 41 ms 26548 KB Output is correct
32 Correct 65 ms 28180 KB Output is correct
33 Correct 74 ms 29320 KB Output is correct
34 Correct 84 ms 30152 KB Output is correct
35 Correct 38 ms 28248 KB Output is correct
36 Correct 77 ms 31052 KB Output is correct
37 Correct 65 ms 30136 KB Output is correct
38 Correct 101 ms 31760 KB Output is correct
39 Correct 64 ms 30112 KB Output is correct
40 Correct 85 ms 31088 KB Output is correct
41 Correct 268 ms 49148 KB Output is correct
42 Correct 886 ms 82872 KB Output is correct
43 Correct 387 ms 67572 KB Output is correct
44 Correct 1111 ms 107072 KB Output is correct
45 Correct 1502 ms 98316 KB Output is correct
46 Correct 829 ms 87472 KB Output is correct
47 Correct 1181 ms 88620 KB Output is correct
48 Correct 740 ms 88248 KB Output is correct
49 Correct 929 ms 88760 KB Output is correct
50 Correct 1008 ms 87980 KB Output is correct
51 Correct 444 ms 64868 KB Output is correct
52 Correct 1070 ms 91392 KB Output is correct
53 Correct 818 ms 88848 KB Output is correct
54 Correct 1723 ms 98540 KB Output is correct
55 Correct 1846 ms 105084 KB Output is correct