#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;
namespace {
const int N_MAX = 20000;
const int pattern[] = {0, 1, 0, 0, 1, 1};
int N, M, A, B;
int edge_u[N_MAX], edge_v[N_MAX];
vector <int> adj[N_MAX];
int other (int i, int u) {
return (u != edge_v[i] ? edge_v[i] : edge_u[i]);
}
int up_edge[N_MAX];
int color[N_MAX + 1];
int chain[N_MAX];
void dfs () {
fill(up_edge, up_edge + N, -1);
up_edge[0] = M; color[M] = 1;
chain[0] = -1;
queue <int> q;
q.push(0);
while (q.empty() == false) {
int u = q.front();
q.pop();
if ((int) adj[u].size() == 2 && u != 0) {
if (chain[u] == -1) {
chain[u] = (1 - color[up_edge[u]]);
} else {
chain[u]++;
}
} else {
chain[u] = -1;
}
for (int i : adj[u]) {
int v = other(i, u);
if (up_edge[v] == -1) {
up_edge[v] = i;
color[i] = (chain[u] == -1 ? 1 - color[up_edge[u]] : pattern[chain[u] % 6]);
chain[v] = chain[u];
q.push(v);
}
}
}
}
int dist[N_MAX];
void bfs () {
fill(dist, dist + N, -1);
up_edge[0] = M; color[M] = 2;
dist[0] = 0;
queue <int> q;
q.push(0);
while (q.empty() == false) {
int u = q.front();
q.pop();
for (int i : adj[u]) {
int v = other(i, u);
if (dist[v] == -1) {
up_edge[v] = i;
dist[v] = dist[u] + 1;
color[i] = (color[up_edge[u]] + 1) % 3;
q.push(v);
} else if (dist[u] <= dist[v]){
color[i] = (color[up_edge[u]] + 1) % 3;
}
}
}
}
}
vector <int> Mark (int _N, int _M, int _A, int _B, vector <int> _U, vector <int> _V) {
N = _N; M = _M; A = _A; B = _B;
for (int i = 0; i < M; i++) {
edge_u[i] = _U[i]; edge_v[i] = _V[i];
adj[edge_u[i]].push_back(i);
adj[edge_v[i]].push_back(i);
}
if (B > 0) {
dfs();
} else {
bfs();
}
vector <int> X(M);
copy(color, color + M, X.begin());
for (int u = 0; u < N; u++) {
adj[u].clear();
up_edge[u] = 0;
}
return X;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;
namespace {
int A, B;
vector <int> cols;
bool passed_test;
}
void Init (int _A, int _B) {
A = _A; B = _B;
cols.clear();
passed_test = false;
}
int Move (vector <int> cnt_col) {
if (B > 0) {
int deg = cnt_col[0] + cnt_col[1] + 1;
// First move
if (cols.empty() == true) {
deg--;
// If leaf, take the only option
if (deg == 1) {
passed_test = true;
cols.push_back((cnt_col[1] > 0 ? 1 : 0));
return cols.back();
}
// If not crossroad, take any option
if (deg == 2) {
cols.push_back((cnt_col[1] > 0 ? 1 : 0));
return cols.back();
}
// If crossroad, take the only option with frequency 1
passed_test = true;
cols.push_back((cnt_col[1] == 1 ? 1 : 0));
return cols.back();
}
// If leaf, turn back
if (deg == 1) {
passed_test = true;
cols = {cols.back()};
return -1;
}
// If not crossroad, check for pattern
if (deg == 2) {
cols.push_back((cnt_col[1] > 0 ? 1 : 0));
if (passed_test == false && (int) cols.size() == 6) {
int ok = -1;
for (int i = 0; i < 6; i++) {
if (cols[i] == 0 && cols[(i + 1) % 6] == 0) {
ok = (cols[(i + 2) % 6] != cols[(i + 3) % 6]);
break;
}
}
assert(ok != -1);
passed_test = true;
if (ok == false) {
cols.pop_back();
cols = {cols.back()};
return -1;
}
}
return cols.back();
}
// If crossroad, check for count
passed_test = true;
if (cnt_col[0] == 0 || cnt_col[1] == 0) {
cols = {cols.back()};
return -1;
} else {
cols.push_back(1 - cols.back());
return cols.back();
}
} else {
if ((cnt_col[0] > 0) + (cnt_col[1] > 0) + (cnt_col[2] > 0) == 1) {
return (cnt_col[0] > 0 ? 0 : (cnt_col[1] > 0 ? 1 : 2));
} else {
return (cnt_col[0] == 0 ? 1 : (cnt_col[1] == 0 ? 2 : 0));
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
15952 KB |
Output is correct |
2 |
Correct |
2 ms |
1468 KB |
Output is correct |
3 |
Correct |
24 ms |
15468 KB |
Output is correct |
4 |
Correct |
37 ms |
16952 KB |
Output is correct |
5 |
Correct |
34 ms |
16944 KB |
Output is correct |
6 |
Correct |
27 ms |
15808 KB |
Output is correct |
7 |
Correct |
30 ms |
15736 KB |
Output is correct |
8 |
Correct |
32 ms |
16500 KB |
Output is correct |
9 |
Correct |
32 ms |
16432 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
15952 KB |
Output is correct |
2 |
Correct |
2 ms |
1468 KB |
Output is correct |
3 |
Correct |
24 ms |
15468 KB |
Output is correct |
4 |
Correct |
37 ms |
16952 KB |
Output is correct |
5 |
Correct |
34 ms |
16944 KB |
Output is correct |
6 |
Correct |
27 ms |
15808 KB |
Output is correct |
7 |
Correct |
30 ms |
15736 KB |
Output is correct |
8 |
Correct |
32 ms |
16500 KB |
Output is correct |
9 |
Correct |
32 ms |
16432 KB |
Output is correct |
10 |
Correct |
26 ms |
13688 KB |
Output is correct |
11 |
Correct |
26 ms |
13484 KB |
Output is correct |
12 |
Correct |
27 ms |
13664 KB |
Output is correct |
13 |
Correct |
27 ms |
13492 KB |
Output is correct |
14 |
Correct |
30 ms |
13708 KB |
Output is correct |
15 |
Correct |
28 ms |
14192 KB |
Output is correct |
16 |
Correct |
32 ms |
16508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
13376 KB |
Output is correct |
2 |
Correct |
1 ms |
1308 KB |
Output is correct |
3 |
Correct |
28 ms |
12896 KB |
Output is correct |
4 |
Correct |
36 ms |
14968 KB |
Output is correct |
5 |
Correct |
34 ms |
14900 KB |
Output is correct |
6 |
Correct |
28 ms |
13424 KB |
Output is correct |
7 |
Correct |
27 ms |
13400 KB |
Output is correct |
8 |
Correct |
38 ms |
14192 KB |
Output is correct |
9 |
Correct |
32 ms |
14180 KB |
Output is correct |
10 |
Correct |
28 ms |
13932 KB |
Output is correct |
11 |
Correct |
27 ms |
13940 KB |
Output is correct |
12 |
Correct |
33 ms |
13788 KB |
Output is correct |
13 |
Correct |
33 ms |
14008 KB |
Output is correct |
14 |
Correct |
32 ms |
14200 KB |
Output is correct |
15 |
Correct |
30 ms |
14192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
13376 KB |
Output is correct |
2 |
Correct |
1 ms |
1308 KB |
Output is correct |
3 |
Correct |
28 ms |
12896 KB |
Output is correct |
4 |
Correct |
36 ms |
14968 KB |
Output is correct |
5 |
Correct |
34 ms |
14900 KB |
Output is correct |
6 |
Correct |
28 ms |
13424 KB |
Output is correct |
7 |
Correct |
27 ms |
13400 KB |
Output is correct |
8 |
Correct |
38 ms |
14192 KB |
Output is correct |
9 |
Correct |
32 ms |
14180 KB |
Output is correct |
10 |
Correct |
28 ms |
13932 KB |
Output is correct |
11 |
Correct |
27 ms |
13940 KB |
Output is correct |
12 |
Correct |
33 ms |
13788 KB |
Output is correct |
13 |
Correct |
33 ms |
14008 KB |
Output is correct |
14 |
Correct |
32 ms |
14200 KB |
Output is correct |
15 |
Correct |
30 ms |
14192 KB |
Output is correct |
16 |
Correct |
26 ms |
11956 KB |
Output is correct |
17 |
Correct |
24 ms |
11896 KB |
Output is correct |
18 |
Correct |
25 ms |
11632 KB |
Output is correct |
19 |
Correct |
25 ms |
11884 KB |
Output is correct |
20 |
Correct |
28 ms |
12220 KB |
Output is correct |
21 |
Correct |
27 ms |
12140 KB |
Output is correct |
22 |
Correct |
30 ms |
14448 KB |
Output is correct |
23 |
Correct |
26 ms |
11884 KB |
Output is correct |
24 |
Correct |
26 ms |
11928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
1560 KB |
Output is correct |
2 |
Correct |
1 ms |
1296 KB |
Output is correct |
3 |
Correct |
2 ms |
1560 KB |
Output is correct |
4 |
Correct |
2 ms |
1560 KB |
Output is correct |
5 |
Correct |
2 ms |
1560 KB |
Output is correct |
6 |
Correct |
2 ms |
1560 KB |
Output is correct |
7 |
Correct |
2 ms |
1568 KB |
Output is correct |
8 |
Correct |
2 ms |
1568 KB |
Output is correct |
9 |
Correct |
2 ms |
1568 KB |
Output is correct |
10 |
Correct |
2 ms |
1568 KB |
Output is correct |
11 |
Correct |
2 ms |
1568 KB |
Output is correct |
12 |
Correct |
2 ms |
1564 KB |
Output is correct |
13 |
Correct |
2 ms |
1568 KB |
Output is correct |
14 |
Correct |
2 ms |
1572 KB |
Output is correct |
15 |
Correct |
1 ms |
1564 KB |
Output is correct |
16 |
Correct |
1 ms |
1560 KB |
Output is correct |
17 |
Correct |
2 ms |
1560 KB |
Output is correct |
18 |
Correct |
1 ms |
1564 KB |
Output is correct |
19 |
Correct |
2 ms |
1560 KB |
Output is correct |
20 |
Correct |
2 ms |
1568 KB |
Output is correct |
21 |
Correct |
2 ms |
1564 KB |
Output is correct |
22 |
Correct |
2 ms |
1552 KB |
Output is correct |
23 |
Correct |
3 ms |
1560 KB |
Output is correct |
24 |
Correct |
2 ms |
1568 KB |
Output is correct |
25 |
Correct |
1 ms |
1560 KB |
Output is correct |
26 |
Correct |
2 ms |
1564 KB |
Output is correct |
27 |
Correct |
2 ms |
1568 KB |
Output is correct |
28 |
Correct |
2 ms |
1564 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
11684 KB |
Output is correct |
2 |
Correct |
27 ms |
12080 KB |
Output is correct |
3 |
Correct |
1 ms |
1308 KB |
Output is correct |
4 |
Correct |
22 ms |
11440 KB |
Output is correct |
5 |
Correct |
32 ms |
12936 KB |
Output is correct |
6 |
Correct |
30 ms |
12932 KB |
Output is correct |
7 |
Correct |
37 ms |
12176 KB |
Output is correct |
8 |
Correct |
28 ms |
11928 KB |
Output is correct |
9 |
Correct |
32 ms |
12912 KB |
Output is correct |
10 |
Correct |
31 ms |
12920 KB |
Output is correct |
11 |
Correct |
32 ms |
12928 KB |
Output is correct |
12 |
Correct |
31 ms |
12920 KB |
Output is correct |
13 |
Correct |
30 ms |
12912 KB |
Output is correct |
14 |
Correct |
31 ms |
12848 KB |
Output is correct |
15 |
Correct |
31 ms |
12956 KB |
Output is correct |
16 |
Correct |
31 ms |
12912 KB |
Output is correct |
17 |
Correct |
30 ms |
12676 KB |
Output is correct |
18 |
Correct |
28 ms |
12656 KB |
Output is correct |
19 |
Correct |
28 ms |
12740 KB |
Output is correct |
20 |
Correct |
30 ms |
12600 KB |
Output is correct |
21 |
Correct |
30 ms |
12668 KB |
Output is correct |
22 |
Correct |
27 ms |
12756 KB |
Output is correct |
23 |
Correct |
25 ms |
11640 KB |
Output is correct |
24 |
Correct |
26 ms |
11636 KB |
Output is correct |
25 |
Correct |
26 ms |
11972 KB |
Output is correct |
26 |
Correct |
27 ms |
11884 KB |
Output is correct |
27 |
Correct |
39 ms |
12392 KB |
Output is correct |
28 |
Correct |
30 ms |
12408 KB |
Output is correct |
29 |
Correct |
28 ms |
12452 KB |
Output is correct |
30 |
Correct |
28 ms |
12508 KB |
Output is correct |
31 |
Correct |
25 ms |
11672 KB |
Output is correct |
32 |
Correct |
32 ms |
11640 KB |
Output is correct |
33 |
Correct |
25 ms |
11896 KB |
Output is correct |
34 |
Correct |
29 ms |
11688 KB |
Output is correct |
35 |
Correct |
28 ms |
12400 KB |
Output is correct |
36 |
Correct |
27 ms |
12400 KB |
Output is correct |
37 |
Correct |
27 ms |
12112 KB |
Output is correct |
38 |
Correct |
26 ms |
12328 KB |
Output is correct |
39 |
Correct |
27 ms |
12408 KB |
Output is correct |
40 |
Correct |
26 ms |
12332 KB |
Output is correct |
41 |
Correct |
28 ms |
12648 KB |
Output is correct |
42 |
Correct |
28 ms |
12592 KB |
Output is correct |
43 |
Correct |
30 ms |
12576 KB |
Output is correct |
44 |
Correct |
30 ms |
12568 KB |
Output is correct |
45 |
Correct |
30 ms |
12576 KB |
Output is correct |
46 |
Correct |
28 ms |
12656 KB |
Output is correct |
47 |
Correct |
26 ms |
12144 KB |
Output is correct |
48 |
Correct |
28 ms |
12116 KB |
Output is correct |
49 |
Correct |
28 ms |
12124 KB |
Output is correct |
50 |
Correct |
27 ms |
12144 KB |
Output is correct |
51 |
Correct |
31 ms |
11888 KB |
Output is correct |
52 |
Correct |
25 ms |
11808 KB |
Output is correct |
53 |
Correct |
25 ms |
11960 KB |
Output is correct |
54 |
Correct |
28 ms |
11856 KB |
Output is correct |
55 |
Correct |
26 ms |
11896 KB |
Output is correct |
56 |
Correct |
25 ms |
11896 KB |
Output is correct |
57 |
Correct |
28 ms |
12160 KB |
Output is correct |
58 |
Correct |
31 ms |
12092 KB |
Output is correct |
59 |
Correct |
31 ms |
12116 KB |
Output is correct |
60 |
Correct |
25 ms |
11824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
11648 KB |
Output is correct |
2 |
Correct |
30 ms |
12148 KB |
Output is correct |
3 |
Correct |
1 ms |
1804 KB |
Output is correct |
4 |
Correct |
20 ms |
11372 KB |
Output is correct |
5 |
Correct |
31 ms |
12912 KB |
Output is correct |
6 |
Correct |
30 ms |
12920 KB |
Output is correct |
7 |
Correct |
27 ms |
11904 KB |
Output is correct |
8 |
Correct |
25 ms |
11900 KB |
Output is correct |
9 |
Correct |
34 ms |
13108 KB |
Output is correct |
10 |
Correct |
38 ms |
13128 KB |
Output is correct |
11 |
Correct |
39 ms |
13140 KB |
Output is correct |
12 |
Correct |
33 ms |
13148 KB |
Output is correct |
13 |
Correct |
30 ms |
13124 KB |
Output is correct |
14 |
Correct |
31 ms |
13128 KB |
Output is correct |
15 |
Incorrect |
33 ms |
13148 KB |
Wrong Answer [6] |
16 |
Halted |
0 ms |
0 KB |
- |