답안 #500569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500569 2021-12-31T11:47:35 Z sidon 낙하산 고리들 (IOI12_rings) C++17
100 / 100
471 ms 48288 KB
#include <bits/stdc++.h>
using namespace std;
#define F(X, Y) for(int X = 0; X < Y; X++)
 
array<int, 2> g[1<<20];
int N, p, j;
 
struct Solver {
	int e[1<<20], d[1<<20] = {};
	int maxDeg = 0, cycle = -1, rem = -1;
	void add(int u, int v) {
		if(u == rem || v == rem || maxDeg > 2) return;
		maxDeg = max({maxDeg, ++d[u], ++d[v]});
 
		while(e[u] >= 0) u = e[u];
		while(e[v] >= 0) v = e[v];
		
		if(u == v)
			cycle = cycle < 0 ? u : N;
		else {
			if(e[u] > e[v]) swap(u, v);
			e[u] += e[v], e[v] = u;
		}
	}
	int get() {
		if(maxDeg > 2) return 0;
		return cycle < 0 ? N : e[cycle];
	}
} s[5];
 
void Init(int n) {
	F(i, 5) fill(s[i].e, s[i].e+(N=n), -1);
}
void Link(int A, int B) {
	if(!p) {
		s[0].add(A, B);
		g[j++] = {A, B};
		if(s[0].maxDeg > 2) {
			F(i, N)
				if(s[0].d[i] > 2) s[p=1].rem = i;
			F(k, j) F(i, 2)
				if(g[k][i] == s[1].rem) s[++p].rem = g[k][!i];
			F(i, 4) F(k, j)
				s[i+1].add(g[k][0], g[k][1]);
		}
	} else
		F(i, 4) s[i+1].add(A, B);
}
int CountCritical() {
	int res = 0;
	if(p) F(i, 4)
		res += s[i+1].get() > 0;
	else res = abs(s[0].get());
	return res;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20772 KB Output is correct
2 Correct 10 ms 20940 KB Output is correct
3 Correct 9 ms 20940 KB Output is correct
4 Correct 8 ms 20812 KB Output is correct
5 Correct 8 ms 20940 KB Output is correct
6 Correct 9 ms 20940 KB Output is correct
7 Correct 8 ms 20940 KB Output is correct
8 Correct 8 ms 20940 KB Output is correct
9 Correct 10 ms 20940 KB Output is correct
10 Correct 8 ms 20940 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 35112 KB Output is correct
2 Correct 278 ms 38600 KB Output is correct
3 Correct 164 ms 40396 KB Output is correct
4 Correct 270 ms 48228 KB Output is correct
5 Correct 273 ms 48140 KB Output is correct
6 Correct 256 ms 47872 KB Output is correct
7 Correct 157 ms 40524 KB Output is correct
8 Correct 408 ms 44280 KB Output is correct
9 Correct 471 ms 46788 KB Output is correct
10 Correct 298 ms 47740 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20772 KB Output is correct
2 Correct 10 ms 20940 KB Output is correct
3 Correct 9 ms 20940 KB Output is correct
4 Correct 8 ms 20812 KB Output is correct
5 Correct 8 ms 20940 KB Output is correct
6 Correct 9 ms 20940 KB Output is correct
7 Correct 8 ms 20940 KB Output is correct
8 Correct 8 ms 20940 KB Output is correct
9 Correct 10 ms 20940 KB Output is correct
10 Correct 8 ms 20940 KB Output is correct
11 Correct 9 ms 21004 KB Output is correct
12 Correct 10 ms 21192 KB Output is correct
13 Correct 10 ms 21068 KB Output is correct
14 Correct 9 ms 21068 KB Output is correct
15 Correct 9 ms 21196 KB Output is correct
16 Correct 10 ms 21068 KB Output is correct
17 Correct 10 ms 21124 KB Output is correct
18 Correct 9 ms 21304 KB Output is correct
19 Correct 10 ms 21196 KB Output is correct
20 Correct 10 ms 21068 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20772 KB Output is correct
2 Correct 10 ms 20940 KB Output is correct
3 Correct 9 ms 20940 KB Output is correct
4 Correct 8 ms 20812 KB Output is correct
5 Correct 8 ms 20940 KB Output is correct
6 Correct 9 ms 20940 KB Output is correct
7 Correct 8 ms 20940 KB Output is correct
8 Correct 8 ms 20940 KB Output is correct
9 Correct 10 ms 20940 KB Output is correct
10 Correct 8 ms 20940 KB Output is correct
11 Correct 9 ms 21004 KB Output is correct
12 Correct 10 ms 21192 KB Output is correct
13 Correct 10 ms 21068 KB Output is correct
14 Correct 9 ms 21068 KB Output is correct
15 Correct 9 ms 21196 KB Output is correct
16 Correct 10 ms 21068 KB Output is correct
17 Correct 10 ms 21124 KB Output is correct
18 Correct 9 ms 21304 KB Output is correct
19 Correct 10 ms 21196 KB Output is correct
20 Correct 10 ms 21068 KB Output is correct
21 Correct 18 ms 22288 KB Output is correct
22 Correct 25 ms 23040 KB Output is correct
23 Correct 28 ms 23584 KB Output is correct
24 Correct 28 ms 22888 KB Output is correct
25 Correct 18 ms 22920 KB Output is correct
26 Correct 28 ms 22844 KB Output is correct
27 Correct 28 ms 23320 KB Output is correct
28 Correct 25 ms 22644 KB Output is correct
29 Correct 26 ms 23056 KB Output is correct
30 Correct 28 ms 23564 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 20772 KB Output is correct
2 Correct 10 ms 20940 KB Output is correct
3 Correct 9 ms 20940 KB Output is correct
4 Correct 8 ms 20812 KB Output is correct
5 Correct 8 ms 20940 KB Output is correct
6 Correct 9 ms 20940 KB Output is correct
7 Correct 8 ms 20940 KB Output is correct
8 Correct 8 ms 20940 KB Output is correct
9 Correct 10 ms 20940 KB Output is correct
10 Correct 8 ms 20940 KB Output is correct
11 Correct 132 ms 35112 KB Output is correct
12 Correct 278 ms 38600 KB Output is correct
13 Correct 164 ms 40396 KB Output is correct
14 Correct 270 ms 48228 KB Output is correct
15 Correct 273 ms 48140 KB Output is correct
16 Correct 256 ms 47872 KB Output is correct
17 Correct 157 ms 40524 KB Output is correct
18 Correct 408 ms 44280 KB Output is correct
19 Correct 471 ms 46788 KB Output is correct
20 Correct 298 ms 47740 KB Output is correct
21 Correct 9 ms 21004 KB Output is correct
22 Correct 10 ms 21192 KB Output is correct
23 Correct 10 ms 21068 KB Output is correct
24 Correct 9 ms 21068 KB Output is correct
25 Correct 9 ms 21196 KB Output is correct
26 Correct 10 ms 21068 KB Output is correct
27 Correct 10 ms 21124 KB Output is correct
28 Correct 9 ms 21304 KB Output is correct
29 Correct 10 ms 21196 KB Output is correct
30 Correct 10 ms 21068 KB Output is correct
31 Correct 18 ms 22288 KB Output is correct
32 Correct 25 ms 23040 KB Output is correct
33 Correct 28 ms 23584 KB Output is correct
34 Correct 28 ms 22888 KB Output is correct
35 Correct 18 ms 22920 KB Output is correct
36 Correct 28 ms 22844 KB Output is correct
37 Correct 28 ms 23320 KB Output is correct
38 Correct 25 ms 22644 KB Output is correct
39 Correct 26 ms 23056 KB Output is correct
40 Correct 28 ms 23564 KB Output is correct
41 Correct 113 ms 34344 KB Output is correct
42 Correct 308 ms 41948 KB Output is correct
43 Correct 174 ms 40720 KB Output is correct
44 Correct 201 ms 39168 KB Output is correct
45 Correct 230 ms 41156 KB Output is correct
46 Correct 232 ms 44448 KB Output is correct
47 Correct 408 ms 44840 KB Output is correct
48 Correct 201 ms 41988 KB Output is correct
49 Correct 275 ms 48288 KB Output is correct
50 Correct 303 ms 47684 KB Output is correct
51 Correct 198 ms 37928 KB Output is correct
52 Correct 239 ms 35816 KB Output is correct
53 Correct 167 ms 41384 KB Output is correct
54 Correct 439 ms 40516 KB Output is correct
55 Correct 297 ms 38648 KB Output is correct