# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
802693 |
2023-08-02T13:27:49 Z |
Um_nik |
Stray Cat (JOI20_stray) |
C++17 |
|
57 ms |
16252 KB |
#include "Anthony.h"
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;
namespace {
} // namespace
vector<int> Mark(int N, int M, int A, int B,
vector<int> U, vector<int> V) {
vector<int> X(M, -1);
vector<vector<pii>> g(N, vector<pii>());
for (int i = 0; i < M; i++) {
int u = U[i], v = V[i];
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> dist(N, N);
dist[0] = 0;
vector<int> q;
q.push_back(0);
for (int i = 0; i < (int)q.size(); i++) {
int v = q[i];
for (pii e : g[v]) if (dist[e.first] == N) {
dist[e.first] = dist[v] + 1;
q.push_back(e.first);
}
}
assert((int)q.size() == N);
if (A >= 3) {
for (int i = 0; i < M; i++)
X[i] = min(dist[U[i]], dist[V[i]]) % 3;
} else {
assert(M == N - 1);
vector<int> posInBamboo(N, -1);
for (int i = 0; i < N; i++) {
int v = q[i];
if (i == 0) {
for (auto [u, id] : g[v]) {
X[id] = 0;
}
continue;
}
int deg = (int)g[v].size();
if (deg == 1) continue;
int par = -1;
int parC = -1;
for (auto [u, id] : g[v]) if (dist[u] < dist[v]) {
par = u;
parC = X[id];
}
if (deg == 2) {
if (posInBamboo[par] != -1) {
posInBamboo[v] = (posInBamboo[par] + 1) % 6;
} else {
posInBamboo[v] = parC + 1;
}
int col = (posInBamboo[v] == 0 || posInBamboo[v] == 2 || posInBamboo[v] == 3 ? 0 : 1);
for (auto [u, id] : g[v]) if (u != par)
X[id] = col;
} else {
for (auto [u, id] : g[v]) if (u != par)
X[id] = parC ^ 1;
}
}
}
return X;
}
#include "Catherine.h"
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
namespace {
int A;
bool bambooPart;
vector<int> colors;
bool GoingUp(vector<int> s) {
vector<int> t = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};
// reverse(t.begin(), t.end());
for (int i = 0; i + (int)s.size() <= (int)t.size(); i++) {
bool ok = true;
for (int j = 0; j < (int)s.size(); j++)
ok &= s[j] == t[i + j];
if (ok) return true;
}
return false;
}
} // namespace
void Init(int A, int B) {
::A = A;
::bambooPart = true;
::colors = vector<int>();
}
int Move(std::vector<int> y) {
if (::A > 2) {
int c = 0;
while(c < 3) {
if (y[c] > 0 && y[(c + 2) % 3] == 0) break;
c++;
}
assert(c < 3);
return c;
} else {
if (!::colors.empty()) y[::colors.back()]++;
int deg = y[0] + y[1];
int col = -2;
if (deg == 1) {
::bambooPart = false;
if (::colors.empty()) {
col = (y[0] > 0 ? 0 : 1);
} else {
col = -1;
}
} else if (deg == 2) {
if (!::bambooPart) {
assert(!::colors.empty());
y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
} else {
if ((int)::colors.size() < 4) {
if (!::colors.empty()) y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
if (::colors.empty()) {
y[col]--;
::colors.push_back((y[0] > 0 ? 0 : 1));
}
} else {
y[::colors.back()]--;
col = (y[0] > 0 ? 0 : 1);
vector<int> s = ::colors;
s.push_back(col);
if (!::GoingUp(s)) col = -1;
::bambooPart = false;
}
}
} else {
assert(deg > 2);
::bambooPart = false;
col = (y[0] == 1 ? 0 : 1);
assert(y[col] == 1);
if (!::colors.empty() && ::colors.back() == col) col = -1;
}
if (col == -1) {
int x = ::colors.back();
::colors.push_back(x);
} else {
::colors.push_back(col);
}
return col;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
15304 KB |
Output is correct |
2 |
Correct |
0 ms |
508 KB |
Output is correct |
3 |
Correct |
27 ms |
14420 KB |
Output is correct |
4 |
Correct |
46 ms |
16168 KB |
Output is correct |
5 |
Correct |
43 ms |
16252 KB |
Output is correct |
6 |
Correct |
30 ms |
15088 KB |
Output is correct |
7 |
Correct |
30 ms |
14996 KB |
Output is correct |
8 |
Correct |
52 ms |
15724 KB |
Output is correct |
9 |
Correct |
35 ms |
15640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
15304 KB |
Output is correct |
2 |
Correct |
0 ms |
508 KB |
Output is correct |
3 |
Correct |
27 ms |
14420 KB |
Output is correct |
4 |
Correct |
46 ms |
16168 KB |
Output is correct |
5 |
Correct |
43 ms |
16252 KB |
Output is correct |
6 |
Correct |
30 ms |
15088 KB |
Output is correct |
7 |
Correct |
30 ms |
14996 KB |
Output is correct |
8 |
Correct |
52 ms |
15724 KB |
Output is correct |
9 |
Correct |
35 ms |
15640 KB |
Output is correct |
10 |
Correct |
25 ms |
13012 KB |
Output is correct |
11 |
Correct |
24 ms |
13092 KB |
Output is correct |
12 |
Correct |
26 ms |
13168 KB |
Output is correct |
13 |
Correct |
35 ms |
12972 KB |
Output is correct |
14 |
Correct |
30 ms |
13416 KB |
Output is correct |
15 |
Correct |
41 ms |
13680 KB |
Output is correct |
16 |
Correct |
35 ms |
15824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
12816 KB |
Output is correct |
2 |
Correct |
0 ms |
508 KB |
Output is correct |
3 |
Correct |
29 ms |
12360 KB |
Output is correct |
4 |
Correct |
36 ms |
14072 KB |
Output is correct |
5 |
Correct |
36 ms |
14036 KB |
Output is correct |
6 |
Correct |
27 ms |
12820 KB |
Output is correct |
7 |
Correct |
32 ms |
12764 KB |
Output is correct |
8 |
Correct |
40 ms |
13484 KB |
Output is correct |
9 |
Correct |
40 ms |
13376 KB |
Output is correct |
10 |
Correct |
38 ms |
13196 KB |
Output is correct |
11 |
Correct |
36 ms |
13176 KB |
Output is correct |
12 |
Correct |
36 ms |
13272 KB |
Output is correct |
13 |
Correct |
37 ms |
13216 KB |
Output is correct |
14 |
Correct |
32 ms |
13476 KB |
Output is correct |
15 |
Correct |
34 ms |
13564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
12816 KB |
Output is correct |
2 |
Correct |
0 ms |
508 KB |
Output is correct |
3 |
Correct |
29 ms |
12360 KB |
Output is correct |
4 |
Correct |
36 ms |
14072 KB |
Output is correct |
5 |
Correct |
36 ms |
14036 KB |
Output is correct |
6 |
Correct |
27 ms |
12820 KB |
Output is correct |
7 |
Correct |
32 ms |
12764 KB |
Output is correct |
8 |
Correct |
40 ms |
13484 KB |
Output is correct |
9 |
Correct |
40 ms |
13376 KB |
Output is correct |
10 |
Correct |
38 ms |
13196 KB |
Output is correct |
11 |
Correct |
36 ms |
13176 KB |
Output is correct |
12 |
Correct |
36 ms |
13272 KB |
Output is correct |
13 |
Correct |
37 ms |
13216 KB |
Output is correct |
14 |
Correct |
32 ms |
13476 KB |
Output is correct |
15 |
Correct |
34 ms |
13564 KB |
Output is correct |
16 |
Correct |
26 ms |
11040 KB |
Output is correct |
17 |
Correct |
28 ms |
11112 KB |
Output is correct |
18 |
Correct |
24 ms |
11296 KB |
Output is correct |
19 |
Correct |
26 ms |
11192 KB |
Output is correct |
20 |
Correct |
27 ms |
11900 KB |
Output is correct |
21 |
Correct |
34 ms |
11568 KB |
Output is correct |
22 |
Correct |
34 ms |
13600 KB |
Output is correct |
23 |
Correct |
27 ms |
11392 KB |
Output is correct |
24 |
Correct |
34 ms |
11280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
0 ms |
516 KB |
Output is correct |
3 |
Correct |
0 ms |
896 KB |
Output is correct |
4 |
Correct |
1 ms |
772 KB |
Output is correct |
5 |
Correct |
2 ms |
768 KB |
Output is correct |
6 |
Correct |
2 ms |
768 KB |
Output is correct |
7 |
Correct |
2 ms |
860 KB |
Output is correct |
8 |
Correct |
2 ms |
840 KB |
Output is correct |
9 |
Correct |
2 ms |
768 KB |
Output is correct |
10 |
Correct |
2 ms |
844 KB |
Output is correct |
11 |
Correct |
1 ms |
768 KB |
Output is correct |
12 |
Correct |
2 ms |
772 KB |
Output is correct |
13 |
Correct |
2 ms |
776 KB |
Output is correct |
14 |
Correct |
2 ms |
768 KB |
Output is correct |
15 |
Correct |
2 ms |
772 KB |
Output is correct |
16 |
Correct |
2 ms |
896 KB |
Output is correct |
17 |
Correct |
2 ms |
900 KB |
Output is correct |
18 |
Correct |
2 ms |
776 KB |
Output is correct |
19 |
Correct |
1 ms |
776 KB |
Output is correct |
20 |
Correct |
2 ms |
764 KB |
Output is correct |
21 |
Correct |
0 ms |
764 KB |
Output is correct |
22 |
Correct |
2 ms |
896 KB |
Output is correct |
23 |
Correct |
2 ms |
768 KB |
Output is correct |
24 |
Correct |
2 ms |
768 KB |
Output is correct |
25 |
Correct |
0 ms |
776 KB |
Output is correct |
26 |
Correct |
1 ms |
776 KB |
Output is correct |
27 |
Correct |
1 ms |
776 KB |
Output is correct |
28 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
10996 KB |
Output is correct |
2 |
Correct |
40 ms |
11512 KB |
Output is correct |
3 |
Correct |
2 ms |
508 KB |
Output is correct |
4 |
Correct |
22 ms |
10756 KB |
Output is correct |
5 |
Correct |
40 ms |
12168 KB |
Output is correct |
6 |
Correct |
45 ms |
12156 KB |
Output is correct |
7 |
Correct |
33 ms |
11276 KB |
Output is correct |
8 |
Correct |
30 ms |
11232 KB |
Output is correct |
9 |
Correct |
41 ms |
12248 KB |
Output is correct |
10 |
Correct |
34 ms |
12156 KB |
Output is correct |
11 |
Correct |
28 ms |
12268 KB |
Output is correct |
12 |
Correct |
41 ms |
12116 KB |
Output is correct |
13 |
Correct |
30 ms |
12204 KB |
Output is correct |
14 |
Correct |
36 ms |
12140 KB |
Output is correct |
15 |
Correct |
32 ms |
12280 KB |
Output is correct |
16 |
Correct |
33 ms |
12208 KB |
Output is correct |
17 |
Correct |
36 ms |
11848 KB |
Output is correct |
18 |
Correct |
27 ms |
11880 KB |
Output is correct |
19 |
Correct |
28 ms |
11800 KB |
Output is correct |
20 |
Correct |
27 ms |
12252 KB |
Output is correct |
21 |
Correct |
40 ms |
12256 KB |
Output is correct |
22 |
Correct |
32 ms |
12256 KB |
Output is correct |
23 |
Correct |
27 ms |
11540 KB |
Output is correct |
24 |
Correct |
30 ms |
11520 KB |
Output is correct |
25 |
Correct |
30 ms |
11532 KB |
Output is correct |
26 |
Correct |
30 ms |
11680 KB |
Output is correct |
27 |
Correct |
31 ms |
12016 KB |
Output is correct |
28 |
Correct |
39 ms |
12044 KB |
Output is correct |
29 |
Correct |
34 ms |
12052 KB |
Output is correct |
30 |
Correct |
33 ms |
12092 KB |
Output is correct |
31 |
Correct |
28 ms |
11412 KB |
Output is correct |
32 |
Correct |
38 ms |
11524 KB |
Output is correct |
33 |
Correct |
34 ms |
11584 KB |
Output is correct |
34 |
Correct |
36 ms |
11600 KB |
Output is correct |
35 |
Correct |
36 ms |
11944 KB |
Output is correct |
36 |
Correct |
45 ms |
12004 KB |
Output is correct |
37 |
Correct |
35 ms |
11920 KB |
Output is correct |
38 |
Correct |
30 ms |
12052 KB |
Output is correct |
39 |
Correct |
47 ms |
11944 KB |
Output is correct |
40 |
Correct |
32 ms |
11912 KB |
Output is correct |
41 |
Correct |
45 ms |
12128 KB |
Output is correct |
42 |
Correct |
45 ms |
12264 KB |
Output is correct |
43 |
Correct |
33 ms |
12192 KB |
Output is correct |
44 |
Correct |
30 ms |
12380 KB |
Output is correct |
45 |
Correct |
35 ms |
12188 KB |
Output is correct |
46 |
Correct |
32 ms |
12208 KB |
Output is correct |
47 |
Correct |
32 ms |
11736 KB |
Output is correct |
48 |
Correct |
38 ms |
11932 KB |
Output is correct |
49 |
Correct |
39 ms |
11752 KB |
Output is correct |
50 |
Correct |
32 ms |
11916 KB |
Output is correct |
51 |
Correct |
33 ms |
11672 KB |
Output is correct |
52 |
Correct |
28 ms |
11696 KB |
Output is correct |
53 |
Correct |
26 ms |
11648 KB |
Output is correct |
54 |
Correct |
27 ms |
11608 KB |
Output is correct |
55 |
Correct |
30 ms |
11728 KB |
Output is correct |
56 |
Correct |
32 ms |
11672 KB |
Output is correct |
57 |
Correct |
35 ms |
11460 KB |
Output is correct |
58 |
Correct |
39 ms |
11452 KB |
Output is correct |
59 |
Correct |
38 ms |
11564 KB |
Output is correct |
60 |
Correct |
36 ms |
11564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
11424 KB |
Output is correct |
2 |
Correct |
34 ms |
11692 KB |
Output is correct |
3 |
Correct |
1 ms |
584 KB |
Output is correct |
4 |
Correct |
25 ms |
11048 KB |
Output is correct |
5 |
Correct |
39 ms |
12584 KB |
Output is correct |
6 |
Correct |
43 ms |
12592 KB |
Output is correct |
7 |
Correct |
30 ms |
11672 KB |
Output is correct |
8 |
Correct |
34 ms |
11644 KB |
Output is correct |
9 |
Correct |
38 ms |
12608 KB |
Output is correct |
10 |
Correct |
40 ms |
12548 KB |
Output is correct |
11 |
Correct |
40 ms |
12624 KB |
Output is correct |
12 |
Correct |
45 ms |
12552 KB |
Output is correct |
13 |
Correct |
45 ms |
12568 KB |
Output is correct |
14 |
Correct |
37 ms |
12600 KB |
Output is correct |
15 |
Correct |
34 ms |
12536 KB |
Output is correct |
16 |
Correct |
40 ms |
12580 KB |
Output is correct |
17 |
Correct |
37 ms |
12348 KB |
Output is correct |
18 |
Correct |
38 ms |
12240 KB |
Output is correct |
19 |
Correct |
31 ms |
12208 KB |
Output is correct |
20 |
Correct |
38 ms |
12264 KB |
Output is correct |
21 |
Correct |
28 ms |
12232 KB |
Output is correct |
22 |
Correct |
28 ms |
12288 KB |
Output is correct |
23 |
Correct |
27 ms |
11376 KB |
Output is correct |
24 |
Correct |
25 ms |
11408 KB |
Output is correct |
25 |
Correct |
30 ms |
11708 KB |
Output is correct |
26 |
Correct |
28 ms |
11688 KB |
Output is correct |
27 |
Correct |
41 ms |
12012 KB |
Output is correct |
28 |
Correct |
37 ms |
11984 KB |
Output is correct |
29 |
Correct |
30 ms |
12048 KB |
Output is correct |
30 |
Correct |
32 ms |
12216 KB |
Output is correct |
31 |
Correct |
33 ms |
11584 KB |
Output is correct |
32 |
Correct |
42 ms |
11368 KB |
Output is correct |
33 |
Correct |
37 ms |
11568 KB |
Output is correct |
34 |
Correct |
40 ms |
11668 KB |
Output is correct |
35 |
Correct |
43 ms |
11992 KB |
Output is correct |
36 |
Correct |
43 ms |
11972 KB |
Output is correct |
37 |
Correct |
40 ms |
12012 KB |
Output is correct |
38 |
Correct |
57 ms |
11944 KB |
Output is correct |
39 |
Correct |
30 ms |
11988 KB |
Output is correct |
40 |
Correct |
35 ms |
11972 KB |
Output is correct |
41 |
Correct |
42 ms |
12216 KB |
Output is correct |
42 |
Correct |
30 ms |
12412 KB |
Output is correct |
43 |
Correct |
36 ms |
12192 KB |
Output is correct |
44 |
Correct |
41 ms |
12348 KB |
Output is correct |
45 |
Correct |
44 ms |
12352 KB |
Output is correct |
46 |
Correct |
38 ms |
12244 KB |
Output is correct |
47 |
Correct |
41 ms |
11896 KB |
Output is correct |
48 |
Correct |
43 ms |
11812 KB |
Output is correct |
49 |
Correct |
34 ms |
11908 KB |
Output is correct |
50 |
Correct |
38 ms |
11904 KB |
Output is correct |
51 |
Correct |
40 ms |
11524 KB |
Output is correct |
52 |
Correct |
26 ms |
11728 KB |
Output is correct |
53 |
Correct |
40 ms |
11664 KB |
Output is correct |
54 |
Correct |
28 ms |
11652 KB |
Output is correct |
55 |
Correct |
30 ms |
11760 KB |
Output is correct |
56 |
Correct |
32 ms |
11708 KB |
Output is correct |
57 |
Correct |
30 ms |
11592 KB |
Output is correct |
58 |
Correct |
37 ms |
11628 KB |
Output is correct |
59 |
Correct |
30 ms |
11536 KB |
Output is correct |
60 |
Correct |
28 ms |
11628 KB |
Output is correct |