Submission #961669

#	Time	Username	Problem	Language	Result	Execution time	Memory
961669		alextodoran	Stray Cat (JOI20_stray)	C++17	100 / 100	40 ms	17312 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];

int chain[N_MAX];

void dfs () {
    fill(up_edge, up_edge + N, -1);
    up_edge[0] = M; color[M] = 1 - N % 2;
    chain[0] = -1;
    queue <int> q;
    q.push(0);
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        if ((int) adj[u].size() == 2 && u != 0) {
            if (chain[u] == -1) {
                chain[u] = (1 - color[up_edge[u]]);
            } else {
                chain[u]++;
            }
        } else {
            chain[u] = -1;
        }
        for (int i : adj[u]) {
            int v = other(i, u);
            if (up_edge[v] == -1) {
                up_edge[v] = i;
                color[i] = (chain[u] == -1 ? 1 - color[up_edge[u]] : pattern[chain[u] % 6]);
                chain[v] = chain[u];
                q.push(v);
            }
        }
    }
}

int dist[N_MAX];
void bfs () {
    fill(dist, dist + N, -1);
    up_edge[0] = M; color[M] = 2;
    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());
    for (int u = 0; u < N; u++) {
        adj[u].clear();
        up_edge[u] = 0;
    }
    return X;
}

Catherine

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

using namespace std;

namespace {
    const int pattern[] = {0, 1, 0, 0, 1, 1};
    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 deg = cnt_col[0] + cnt_col[1] + 1;
        // First move
        if (cols.empty() == true) {
            deg--;
            // If leaf, take the only option
            if (deg == 1) {
                passed_test = true;
                cols.push_back((cnt_col[0] > 0 ? 0 : 1));
                return cols.back();
            }
            // If not crossroad, take any option
            if (deg == 2) {
                if (cnt_col[0] == cnt_col[1]) {
                    cols.push_back(1);
                    cols.push_back(0);
                } else if (cnt_col[0] > 0) {
                    cols.push_back(0);
                    cols.push_back(0);
                } else {
                    cols.push_back(1);
                    cols.push_back(1);
                }
                return cols.back();
            }
            // If crossroad, take the only option with frequency 1
            passed_test = true;
            cols.push_back((cnt_col[0] == 1 ? 0 : 1));
            return cols.back();
        }
        // If leaf, turn back
        if (deg == 1) {
            passed_test = true;
            cols = {cols.back()};
            return -1;
        }
        // If not crossroad, check for pattern
        if (deg == 2) {
            cols.push_back((cnt_col[0] > 0 ? 0 : 1));
            if (passed_test == false && (int) cols.size() == 5) {
                int down = false;
                for (int i = 0; i < 6; i++) {
                    down = true;
                    for (int j = 0; j < 5; j++) {
                        if (cols[j] != pattern[(i + j) % 6]) {
                            down = false;
                            break;
                        }
                    }
                    if (down == true) {
                        break;
                    }
                }
                passed_test = true;
                if (down == true) {
                    cols.pop_back();
                    cols = {cols.back()};
                    return -1;
                }
            }
            return cols.back();
        }
        // If crossroad, check for count
        passed_test = true;
        if (cnt_col[0] == 0 || cnt_col[1] == 0) {
            cols = {cols.back()};
            return -1;
        } else {
            cols.push_back(1 - cols.back());
            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: 9 / 9