Submission #212378

#	Time	Username	Problem	Language	Result	Execution time	Memory
212378		dolphingarlic	Stray Cat (JOI20_stray)	C++14	100 / 100	111 ms	16796 KiB

Anthony

#include "Anthony.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

namespace {

vector<int> X, perm = {0, 1, 0, 0, 1, 1};
vector<pair<int, int>> graph[20000];

void mark_tree(int node = 0, int par_id = -1, int depth = 0) {
    if (~par_id) X[par_id] = perm[depth];
    for (pair<int, int> i : graph[node]) if (i.second != par_id) {
        if (graph[node].size() == 2)
            mark_tree(i.first, i.second, (depth + 1) % 6);
        else
            mark_tree(i.first, i.second, 1 ^ perm[depth]);
    }
}

int visited[20000];

void mark_graph() {
    queue<int> q;
    q.push(0);
    visited[0] = 1;
    while (q.size()) {
        int curr = q.front();
        q.pop();
        for (pair<int, int> i : graph[curr]) if (!visited[i.first]) {
            X[i.second] = (visited[curr] - 1) % 3;
            visited[i.first] = visited[curr] + 1;
            q.push(i.first); 
        } else X[i.second] = (visited[i.first] - 1) % 3;
    }
}

}  // namespace

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    FOR(i, 0, M) {
        graph[U[i]].push_back({V[i], i});
        graph[V[i]].push_back({U[i], i});
    }

    X.resize(M);
    if (B) mark_tree();
    else mark_graph();
    return X;
}

Catherine

#include "Catherine.h"

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

namespace {

int A, B, last;
bool going_up;
vector<int> seen;
vector<vector<int>> good = {
    {1, 1, 0, 0, 1},
    {1, 0, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {0, 1, 0, 1, 1},
    {1, 0, 1, 1, 0},
    {0, 1, 1, 0, 0},
};

int move_tree(vector<int> y) {
    vector<int> new_y = y;
    if (~last) new_y[last]++;

    int deg = accumulate(new_y.begin(), new_y.end(), 0);
    if (deg != 2) going_up = true;

    if (going_up) {
        if (deg == 1) {
            if (last == -1) FOR(i, 0, A) if (y[i]) return last = i;
            return -1;
        } else if (deg == 2) {
            FOR(i, 0, A) if (y[i]) return last = i;
        } else {
            FOR(i, 0, A) if (new_y[i] == 1) {
                if (!y[i]) return -1;
                return last = i;
            }
        }
    } else {
        if (~last) {
            FOR(i, 0, A) if (y[i]) {
                seen.push_back(i);
                if (seen.size() < 5) return last = i;
                else {
                    going_up = true;
                    for (vector<int> v : good)
                        if (v == seen) return last = i;
                    return -1;
                }
            }
        } else {
            FOR(i, 0, A) if (y[i]) {
                seen.push_back(i);
                y[i]--;
                FOR(j, 0, A) if (y[j]) {
                    seen.push_back(j);
                    return last = j;
                }
            }
        }
    }
}

int move_graph(vector<int> y) {
    if (~last) y[last]++;
    FOR(i, 0, 3) if (y[i] && y[(i + 1) % 3]) return last = i;
    FOR(i, 0, 3) if (y[i]) return last = i;
}

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    going_up = false;
    last = -1;
}

int Move(vector<int> y) {
    if (B) return move_tree(y);
    return move_graph(y);
}

Compilation message (stderr)

Catherine.cpp: In function 'int {anonymous}::move_tree(std::vector<int>)':
Catherine.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
Catherine.cpp: In function 'int {anonymous}::move_graph(std::vector<int>)':
Catherine.cpp:70:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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