Submission #590856

#	Time	Username	Problem	Language	Result	Execution time	Memory
590856		Namnamseo	Stray Cat (JOI20_stray)	C++17	4 / 100	56 ms	24468 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 par[maxn], pei[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);
            par[y] = x; pei[y] = ei; lev[y] = lev[x]+1;
            q[t++] = y;
        }
    }
}

vi Case1(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);
    }
    bfs();
    static int pec[maxn];
    for (int i=0; i<M; ++i) {
        int a = ev[i].l, b = ev[i].r;
        if (lev[a] == lev[b]) {
            col[i] = (lev[a]+1)%3;
            ++pec[a]; ++pec[b];
        } else {
            col[i] = min(lev[a], lev[b])%3;
        }
    }
    static int q[maxn];
    int f = 0, t = 0;
    for (int i=0; i<N; ++i) if (pec[i] == 1) q[t++] = i;
    while (f < t) {
        int x = q[f++];
        if (pec[x] != 1) continue;
        int d = lev[x], d1 = (d+1)%3;
        for (int ei : es[x]) {
            auto &e = ev[ei];
            int y = e.l+e.r-x;
            if (col[ei] == d1 && lev[y] == d) {
                col[ei] = d%3;
                --pec[y];
                if (pec[y] == 1) q[t++] = y;
            }
        }
    }
    return vi(col, col+M);
}

}  // namespace

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

Catherine

#include "Catherine.h"
#include <cassert>
#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] == 1) ++oc;
    if (oc == 1) for (int i=0; i<3; ++i) if (y[i] == 1) return i;
    assert(oc == 2);

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

}  // namespace

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

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

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