oj.uz

Submission #590913

# Submission time Handle Problem Language Result Execution time Memory
590913 2022-07-06T14:08:51 Z Namnamseo Stray Cat (JOI20_stray) C++17
15 / 100
 54 ms 17152 KB 
#include "Anthony.h"
#include <bitset>
#include <vector>
using namespace std;
using vi=vector<int>;

namespace {
const int maxn = int(2e4) + 10;

int n;

struct Edge { int l, r; } ev[maxn];
vector<int> es[maxn];
int lev[maxn];
int col[maxn];

void bfs() {
    static int q[maxn];
    static bitset<maxn> vis;
    int f = 0, t = 1; vis.set(0);
    while (f < t) {
        int x = q[f++];
        for (int ei : es[x]) {
            int y = ev[ei].l + ev[ei].r - x;
            if (vis[y]) continue;
            vis.set(y);
            lev[y] = lev[x]+1;
            q[t++] = y;
        }
    }
}

void Read(int N, int M, vi &U, vi &V) {
    n = N;
    for (int i=0; i<M; ++i) {
        ev[i] = {U[i], V[i]};
        es[U[i]].push_back(i);
        es[V[i]].push_back(i);
    }
}

vi Case1(int N, int M, vi &U, vi &V) {
    Read(N, M, U, V);
    bfs();

    for (int i=0; i<M; ++i) {
        int a = ev[i].l, b = ev[i].r;
        col[i] = min(lev[a], lev[b])%3;
    }
    return vi(col, col+M);
}

const int dict[6] = {0, 1, 1, 0, 0, 1};
void Go(int x, int p, int state) {
    if (es[x].size() == 1u) return;
    if (es[x].size() > 2u) {
        int pc = dict[(state+5)%6];
        for (int ei : es[x]) {
            int y = ev[ei].l + ev[ei].r - x;
            if (y == p) continue;
            col[ei] = pc^1;
            Go(y, x, pc^1);
        }
        return;
    }

    for (int ei : es[x]) {
        int y = ev[ei].l + ev[ei].r - x;
        if (y == p) continue;
        col[ei] = dict[state];
        Go(y, x, (state+1)%6);
    }
}

vi Case2(int N, int M, vi &U, vi &V) {
    Read(N, M, U, V);
    for (int ei : es[0]) {
        int y = ev[ei].l + ev[ei].r;
        Go(y, 0, 1);
    }
    return vi(col, col+M);
}

}  // namespace

namespace {
}  // namespace

vi Mark(int N, int M, int A, int B, vi U, vi V) {
    if (B == 0)
        return Case1(N, M, U, V);
    else
        return Case2(N, M, U, V);
}

#include "Catherine.h"
#include <vector>
using namespace std;
using vi=vector<int>;

namespace {
int A, B;

int Move1(vi &y) {
    int oc = 0;
    for (int i=0; i<3; ++i) if (y[i]) ++oc;
    if (oc == 1) for (int i=0; i<3; ++i) if (y[i]) return i;

    int tmp = 0;
    for (int i=0; i<3; ++i) if (y[i]) tmp += i;
    tmp += 2;
    tmp *= 2;
    return tmp % 3;
}

}  // namespace

namespace {
int last_move;
vector<int> hist;
bool know;
}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    last_move = -1;
}

int Move(vi y) {
    if (B == 0) return Move1(y);

    int last = last_move;
    int which;
    int ec = y[0] + y[1] + (last != -1);

    if (know) {
        if (ec >= 3) which = !last;
        else which = !!y[1];
    } else {
        if (ec >= 3) {
            which = (y[1]+(last==1) == 1);
            if (which == last) which = -1;
            know = true;
        } else if (ec == 1) {
            which = !!(y[1]+(last==1));
            if (which == last) which = -1;
            know = true;
        } else {
            if (last != -1) ++y[last];
            int state = (y[0] == 2) ? 0 :
                      (y[1] == 2) ? 1 : 2;
            if (last != -1) --y[last];
            if (hist.size() == 3u) {
                int t = hist[0]*1000 +
                        hist[1]*100 +
                        hist[2]*10 + state;
                int down_sign = 212022212;
                bool is_down = false;
                for (int i=0; i<6; ++i) {
                    if (down_sign%10000 == t) { is_down = true; break; }
                    down_sign /= 10;
                }
                if (is_down) which = last_move;
                else which = !!y[1];
                know = true;
            } else {
                hist.push_back(state);
                which = !!y[1];
            }
        }
    }

    if (which != -1) last_move = which;
    return which;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16008 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 35 ms 15436 KB Output is correct
4 Correct 48 ms 17152 KB Output is correct
5 Correct 52 ms 17128 KB Output is correct
6 Correct 35 ms 16052 KB Output is correct
7 Correct 36 ms 15816 KB Output is correct
8 Correct 45 ms 16524 KB Output is correct
9 Correct 41 ms 16540 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16008 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 35 ms 15436 KB Output is correct
4 Correct 48 ms 17152 KB Output is correct
5 Correct 52 ms 17128 KB Output is correct
6 Correct 35 ms 16052 KB Output is correct
7 Correct 36 ms 15816 KB Output is correct
8 Correct 45 ms 16524 KB Output is correct
9 Correct 41 ms 16540 KB Output is correct
10 Correct 40 ms 13916 KB Output is correct
11 Correct 36 ms 13840 KB Output is correct
12 Correct 38 ms 13876 KB Output is correct
13 Correct 37 ms 13976 KB Output is correct
14 Correct 35 ms 14140 KB Output is correct
15 Correct 43 ms 14464 KB Output is correct
16 Correct 43 ms 16668 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13632 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 35 ms 13140 KB Output is correct
4 Correct 54 ms 15012 KB Output is correct
5 Correct 44 ms 15096 KB Output is correct
6 Correct 34 ms 13704 KB Output is correct
7 Correct 34 ms 13736 KB Output is correct
8 Correct 39 ms 14268 KB Output is correct
9 Correct 42 ms 14332 KB Output is correct
10 Correct 48 ms 14096 KB Output is correct
11 Correct 39 ms 13988 KB Output is correct
12 Correct 52 ms 14068 KB Output is correct
13 Correct 43 ms 13952 KB Output is correct
14 Correct 46 ms 14196 KB Output is correct
15 Correct 39 ms 14260 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13632 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 35 ms 13140 KB Output is correct
4 Correct 54 ms 15012 KB Output is correct
5 Correct 44 ms 15096 KB Output is correct
6 Correct 34 ms 13704 KB Output is correct
7 Correct 34 ms 13736 KB Output is correct
8 Correct 39 ms 14268 KB Output is correct
9 Correct 42 ms 14332 KB Output is correct
10 Correct 48 ms 14096 KB Output is correct
11 Correct 39 ms 13988 KB Output is correct
12 Correct 52 ms 14068 KB Output is correct
13 Correct 43 ms 13952 KB Output is correct
14 Correct 46 ms 14196 KB Output is correct
15 Correct 39 ms 14260 KB Output is correct
16 Correct 28 ms 12096 KB Output is correct
17 Correct 30 ms 12040 KB Output is correct
18 Correct 32 ms 12032 KB Output is correct
19 Correct 34 ms 11988 KB Output is correct
20 Correct 48 ms 12624 KB Output is correct
21 Correct 37 ms 12376 KB Output is correct
22 Correct 41 ms 14452 KB Output is correct
23 Correct 31 ms 12168 KB Output is correct
24 Correct 32 ms 12084 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1336 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 1 ms 1388 KB Output is correct
4 Correct 2 ms 1284 KB Output is correct
5 Correct 2 ms 1380 KB Output is correct
6 Correct 2 ms 1284 KB Output is correct
7 Correct 2 ms 1292 KB Output is correct
8 Correct 2 ms 1284 KB Output is correct
9 Correct 2 ms 1284 KB Output is correct
10 Incorrect 2 ms 1284 KB Wrong Answer [5]
11 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 11248 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 11388 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -