Submission #590921

#	Time	Username	Problem	Language	Result	Execution time	Memory
590921		Namnamseo	Stray Cat (JOI20_stray)	C++17	100 / 100	45 ms	16868 KiB

Anthony

#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, 1+(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);
}

Catherine

#include "Catherine.h"
#include <cstdio>
#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];
                if (which == last) which = -1;
                know = true;
            } else {
                hist.push_back(state);
                which = !!y[1];
            }
        }
    }

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

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9