| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 400907 |
2021-05-08T19:51:55 Z |
12tqian |
Stray Cat (JOI20_stray) |
C++17 |
|
66 ms |
17480 KB |
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;
// 0 -> 1 -> 2
vi Mark(int n, int m, int a, int b, vi U, vi V) {
vector<vi> g(n);
auto cp = [&](int u, int v) -> pi {
if (u > v) swap(u, v);
return mp(u, v);
};
map<pi, int> conv;
vpi ed;
vi res(m);
f0r(i, m) {
int u = U[i];
int v = V[i];
conv[cp(u, v)] = i;
g[u].pb(v);
g[v].pb(u);
ed.pb(cp(u, v));
}
if (a >= 3) { // bfs work
vi dist(n, -1);
list<int> que;
dist[0] = 0;
que.pb(0);
while (!que.empty()) {
int u = que.front();
que.pop_front();
each(v, g[u]) {
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
que.push_back(v);
}
}
each(e, ed) {
int u = e.f;
int v = e.s;
int id = conv[cp(u, v)];
if (dist[u] == dist[v]) {
res[id] = dist[u] % 3;
} else {
if (dist[u] > dist[v]) {
swap(u, v);
}
res[id] = dist[u] % 3;
}
}
} else {
vi par(n);
function<void(int, int)> dfs_precomp = [&](int u, int p) {
par[u] = p;
each(v, g[u]) {
if (v == p) continue;
dfs_precomp(v, u);
}
};
dfs_precomp(0, -1);
vi lab(n);
function<void(int, int, int)> dfs_label = [&](int u, int p, int d) {
if (u == 0) {
each(v, g[u]) {
if (v == p) continue;
lab[v] = 0;
dfs_label(v, u, 0);
}
return;
}
if (sz(g[u]) == 1) return;
if (sz(g[u]) > 2) {
each(v, g[u]) {
if (v == p) continue;
lab[v] = lab[u] ^ 1;
dfs_label(v, u, 0);
}
} else {
each(v, g[u]) {
if (v == p) continue;
if (d == 0 || d == 2 || d == 5) {
lab[v] = lab[u] ^ 1;
} else {
lab[v] = lab[u];
}
dfs_label(v, u, (d + 1) % 6);
}
}
};
dfs_label(0, -1, -1);
f1r(i, 1, n) {
int id = conv[cp(i, par[i])];
res[id] = lab[i];
}
}
return res;
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using ll = long long;
namespace {
int a, b;
vi moves;
vpi seen;
bool oriented = false;
} // namespace
void Init(int A, int B) {
::a = A;
::b = B;
}
int MoveT(vi& v) {
int x = v[0];
int y = v[1];
pi use = {x, y};
if (sz(moves)) {
if (moves.back() == 0) use.f++;
else use.s++;
}
seen.pb(use);
#define R(k) moves.pb(k); return k;
#define F() if (x) { R(0); } else { R(1); }
// R is for moving to a color
// F is if you're on a line, move forward
if (oriented) { // if you're already oriented
// assert(x || y);
if (x == 0) {
R(1);
} else if (y == 0) {
R(0);
}
if (sz(moves)) {
if (moves.back() == 0) x++;
else y++;
}
if (x > y) {
assert(y == 1);
R(1);
} else if (x < y) {
assert(x == 1);
R(0);
}
assert(false);
R(-1); // shouldn't reach here
}
{ // checking if you're already at a good place
if (x == 0 && y == 0) { // dead end leaf node
oriented = true;
R(-1);
}
if (sz(moves)) {
if (moves.back() == 0) x++;
else y++;
}
if (x == 0 && y == 1) { // leaf nodes
oriented = true;
R(1);
} else if (y == 0 && x == 1) {
oriented = true;
R(0);
}
if (x > y) { // you already reached a good place
oriented = true;
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
if (y == 0) {
R(-1);
}
else {
R(1);
}
} else if (x < y) {
oriented = true;
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
if (x == 0) {
R(-1);
} else {
R(0);
}
}
if (sz(moves)) {
if (moves.back() == 0) x--;
else y--;
}
}
int did = sz(moves);
if (did == 0) { // first move
F();
} else if (did == 1) {
if (seen[0].f == seen[0].s) { // 0 1, went 0 before
if (x) { // go 0 if possible
R(0);
} else {
R(-1);
}
} else { // same things
if (moves.back() == 0 && x) {
R(-1);
} else if (moves.back() == 1 && y) {
R(-1);
} else {
F();
}
}
} else if (did == 2) {
if (moves.back() == -1) {
F();
} else {
R(-1);
}
} else if (did == 3) {
if (moves.back() == -1) {
R(-1);
} else {
F();
}
} else if (did == 4) {
if (moves.back() == -1) {
F();
} else {
R(-1);
}
} else if (did == 5) {
R(-1);
} else if (did == 6) {
oriented = true;
vi came; // direction just came from
vi other; // other direction
{ // came
if (moves[4] == -1 && moves[5] == -1) {
came.pb(moves[2]);
came.pb(moves[3]);
if (seen[4].f >= 2) {
came.pb(0);
} else if (seen[4].s >= 2) {
came.pb(1);
} else {
came.pb(came.back() ^ 1);
}
} else {
came.pb(moves[4]);
if (seen[5].f >= 2) {
came.pb(0);
} else if (seen[5].s >= 2) {
came.pb(1);
} else {
came.pb(came.back() ^ 1);
}
}
}
{ // other
if (moves[0] != -1 && moves[1] != -1) {
other.pb(moves[0]);
other.pb(moves[1]);
if (seen[2].f >= 2) {
other.pb(0);
} else if (seen[2].s >= 2) {
other.pb(1);
} else {
other.pb(other.back() ^ 1);
}
} else {
other.pb(moves[0]);
if (seen[1].f >= 2) {
other.pb(0);
} else if (seen[1].s >= 2) {
other.pb(1);
} else {
other.pb(other.back() ^ 1);
}
}
}
vi comb = came;
reverse(all(comb));
each(x, other) comb.pb(x);
vi use;
int i1 = 0;
int i2 = 0;
int sz = sz(comb);
while (i1 != sz) {
while (i2 < sz - 1 && comb[i2 + 1] == comb[i2]) ++i2;
use.pb(i2 - i1 + 1);
i1 = ++i2;
}
int num = 0;
each(x, use) x += num;
assert(num == 5);
if (sz(use) == 2) {
int x = use[0];
int y = use[1];
if (x == 2) {
R(-1);
} else {
F();
}
} else if (sz(use) == 3) {
int x = use[0];
int y = use[1];
int z = use[2];
if (x == 1) {
if (y == 2) {
R(-1);
} else if (y == 1) {
F();
} else {
assert(false);
}
} else if (x == 2) {
if (y == 2) {
F();
} else {
assert(false);
}
} else if (x == 3) {
R(-1);
}
}
} else {
assert(false);
}
while (true) {} // stall time
assert(false);
R(-1);
}
int MoveG(vi& y) {
int a0 = y[0];
int a1 = y[1];
int a2 = y[2];
if (a0 && a1) {
return 0;
} else if (a1 && a2) {
return 1;
} else if (a2 && a0) {
return 2;
} else if (a0) {
return 0;
} else if (a1) {
return 1;
} else if (a2) {
return 2;
}
return -1;
}
int Move(vi y) {
if (a >= 3) {
return MoveG(y);
} else {
return MoveT(y);
}
}
Compilation message
Catherine.cpp: In function 'int MoveT(vi&)':
Catherine.cpp:239:17: warning: unused variable 'y' [-Wunused-variable]
239 | int y = use[1];
| ^
Catherine.cpp:248:17: warning: unused variable 'z' [-Wunused-variable]
248 | int z = use[2];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
16296 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
48 ms |
16352 KB |
Output is correct |
| 4 |
Correct |
66 ms |
17464 KB |
Output is correct |
| 5 |
Correct |
66 ms |
17480 KB |
Output is correct |
| 6 |
Correct |
56 ms |
16208 KB |
Output is correct |
| 7 |
Correct |
56 ms |
16248 KB |
Output is correct |
| 8 |
Correct |
61 ms |
16900 KB |
Output is correct |
| 9 |
Correct |
61 ms |
16908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
16296 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
48 ms |
16352 KB |
Output is correct |
| 4 |
Correct |
66 ms |
17464 KB |
Output is correct |
| 5 |
Correct |
66 ms |
17480 KB |
Output is correct |
| 6 |
Correct |
56 ms |
16208 KB |
Output is correct |
| 7 |
Correct |
56 ms |
16248 KB |
Output is correct |
| 8 |
Correct |
61 ms |
16900 KB |
Output is correct |
| 9 |
Correct |
61 ms |
16908 KB |
Output is correct |
| 10 |
Correct |
53 ms |
14216 KB |
Output is correct |
| 11 |
Correct |
52 ms |
14328 KB |
Output is correct |
| 12 |
Correct |
52 ms |
14220 KB |
Output is correct |
| 13 |
Correct |
52 ms |
14240 KB |
Output is correct |
| 14 |
Correct |
53 ms |
14348 KB |
Output is correct |
| 15 |
Correct |
56 ms |
14736 KB |
Output is correct |
| 16 |
Correct |
60 ms |
17036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
14088 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
47 ms |
13852 KB |
Output is correct |
| 4 |
Correct |
62 ms |
15332 KB |
Output is correct |
| 5 |
Correct |
63 ms |
15396 KB |
Output is correct |
| 6 |
Correct |
54 ms |
13956 KB |
Output is correct |
| 7 |
Correct |
54 ms |
14044 KB |
Output is correct |
| 8 |
Correct |
59 ms |
14636 KB |
Output is correct |
| 9 |
Correct |
59 ms |
14668 KB |
Output is correct |
| 10 |
Correct |
55 ms |
14452 KB |
Output is correct |
| 11 |
Correct |
55 ms |
14348 KB |
Output is correct |
| 12 |
Correct |
56 ms |
14340 KB |
Output is correct |
| 13 |
Correct |
56 ms |
14468 KB |
Output is correct |
| 14 |
Correct |
59 ms |
14608 KB |
Output is correct |
| 15 |
Correct |
57 ms |
14700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
14088 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
47 ms |
13852 KB |
Output is correct |
| 4 |
Correct |
62 ms |
15332 KB |
Output is correct |
| 5 |
Correct |
63 ms |
15396 KB |
Output is correct |
| 6 |
Correct |
54 ms |
13956 KB |
Output is correct |
| 7 |
Correct |
54 ms |
14044 KB |
Output is correct |
| 8 |
Correct |
59 ms |
14636 KB |
Output is correct |
| 9 |
Correct |
59 ms |
14668 KB |
Output is correct |
| 10 |
Correct |
55 ms |
14452 KB |
Output is correct |
| 11 |
Correct |
55 ms |
14348 KB |
Output is correct |
| 12 |
Correct |
56 ms |
14340 KB |
Output is correct |
| 13 |
Correct |
56 ms |
14468 KB |
Output is correct |
| 14 |
Correct |
59 ms |
14608 KB |
Output is correct |
| 15 |
Correct |
57 ms |
14700 KB |
Output is correct |
| 16 |
Correct |
49 ms |
12644 KB |
Output is correct |
| 17 |
Correct |
49 ms |
12536 KB |
Output is correct |
| 18 |
Correct |
50 ms |
12288 KB |
Output is correct |
| 19 |
Correct |
50 ms |
12224 KB |
Output is correct |
| 20 |
Correct |
55 ms |
12828 KB |
Output is correct |
| 21 |
Correct |
52 ms |
12580 KB |
Output is correct |
| 22 |
Correct |
56 ms |
14796 KB |
Output is correct |
| 23 |
Correct |
51 ms |
12288 KB |
Output is correct |
| 24 |
Correct |
52 ms |
12340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
876 KB |
Output is correct |
| 2 |
Correct |
2 ms |
500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
880 KB |
Output is correct |
| 4 |
Correct |
2 ms |
876 KB |
Output is correct |
| 5 |
Correct |
2 ms |
876 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
880 KB |
Wrong Answer [5] |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
12204 KB |
Output is correct |
| 2 |
Incorrect |
50 ms |
13452 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
12216 KB |
Output is correct |
| 2 |
Correct |
55 ms |
13708 KB |
Output is correct |
| 3 |
Correct |
2 ms |
488 KB |
Output is correct |
| 4 |
Correct |
43 ms |
11956 KB |
Output is correct |
| 5 |
Correct |
63 ms |
15988 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
14788 KB |
Wrong Answer [4] |
| 7 |
Halted |
0 ms |
0 KB |
- |
