Submission #960926

#	Time	Username	Problem	Language	Result	Execution time	Memory
960926		alextodoran	Stray Cat (JOI20_stray)	C++17	91 / 100	40 ms	16932 KiB

Anthony

#include <bits/stdc++.h>
#include "Anthony.h"

using namespace std;

namespace {

const int N_MAX = 20000;
const int pattern[] = {0, 1, 0, 0, 1, 1};

int N, M, A, B;
int edge_u[N_MAX], edge_v[N_MAX];
vector <int> adj[N_MAX];
int other (int i, int u) {
    return (u != edge_v[i] ? edge_v[i] : edge_u[i]);
}

int up_edge[N_MAX];
int color[N_MAX + 1];

void dfs (int u, int chain = -1) {
    if ((int) adj[u].size() == 2 && u != 0) {
        if (chain == -1) {
            chain = 1 - color[up_edge[u]];
        } else {
            chain++;
        }
    } else {
        chain = -1;
    }
    for (int i : adj[u]) {
        if (i != up_edge[u]) {
            int v = other(i, u);
            up_edge[v] = i;
            color[i] = (chain == -1 ? 1 - color[up_edge[u]] : pattern[chain % 6]);
            dfs(v, chain);
        }
    }
}
void dfs () {
    up_edge[0] = N; color[0] = 0;
    dfs(0);
}

int dist[N_MAX];
void bfs () {
    fill(dist, dist + N, -1);
    up_edge[0] = N; color[0] = 0;
    dist[0] = 0;
    queue <int> q;
    q.push(0);
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        for (int i : adj[u]) {
            int v = other(i, u);
            if (dist[v] == -1) {
                up_edge[v] = i;
                dist[v] = dist[u] + 1;
                color[i] = (color[up_edge[u]] + 1) % 3;
                q.push(v);
            } else if (dist[u] <= dist[v]){
                color[i] = (color[up_edge[u]] + 1) % 3;
            }
        }
    }
}

}

vector <int> Mark (int _N, int _M, int _A, int _B, vector <int> _U, vector <int> _V) {
    N = _N; M = _M; A = _A; B = _B;
    for (int i = 0; i < M; i++) {
        edge_u[i] = _U[i]; edge_v[i] = _V[i];
        adj[edge_u[i]].push_back(i);
        adj[edge_v[i]].push_back(i);
    }
    if (B > 0) {
        dfs();
    } else {
        bfs();
    }
    vector <int> X(M);
    copy(color, color + M, X.begin());
    return X;
}

Catherine

#include <bits/stdc++.h>
#include "Catherine.h"

using namespace std;

namespace {
    int A, B;
    vector <int> cols;
    bool passed_test;
}


void Init (int _A, int _B) {
    A = _A; B = _B;
    cols.clear();
    passed_test = false;
}

int Move (vector <int> cnt_col) {
    if (B > 0) {
        int now = (cols.empty() == false ? 1 - cols.back() : 0);
        if (cnt_col[now] > 0) {
            cols.push_back(now);
        } else if (cnt_col[1 - now] > 0) {
            cols.push_back(1 - now);
        } else {
            passed_test = true;
            cols = {cols.back()};
            return -1;
        }
        int deg = cnt_col[0] + cnt_col[1] + ((int) cols.size() != 1);
        if (cnt_col[cols.back()] > 1 && deg > 2) {
            if ((int) cols.size() == 1) {
                cols.back() = 1 - cols.back();
            } else {
                passed_test = true;
                cols = {cols.back()};
                return -1;
            }
        }
        if (passed_test == false && (int) cols.size() == 6) {
            passed_test = true;
            bool ok = true;
            for (int i = 0; i < (int) cols.size(); i++) {
                if (cols[i] == 0 && cols[(i + 1) % 6] == 0) {
                    ok = (cols[(i + 2) % 6] != cols[(i + 3) % 6]);
                }
            }
            if (ok == false) {
                cols.pop_back();
                cols = {cols.back()};
                return -1;
            }
        }
        return cols.back();
    } else {
        if ((cnt_col[0] > 0) + (cnt_col[1] > 0) + (cnt_col[2] > 0) == 1) {
            return (cnt_col[0] > 0 ? 0 : (cnt_col[1] > 0 ? 1 : 2));
        } else {
            return (cnt_col[0] == 0 ? 1 : (cnt_col[1] == 0 ? 2 : 0));
        }
    }
}

• 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: 0 / 9