Submission #251882

#	Time	Username	Problem	Language	Result	Execution time	Memory
251882		imeimi2000	Stray Cat (JOI20_stray)	C++17	15 / 100	76 ms	17256 KiB

Anthony

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

using namespace std;

static vector<int> edge[20000];
static int par[20000], pc[20000], ord[20000];
void dfs(int x, int p) {
    par[x] = p;
    ord[x] = -1;
    if (!x) {
        for (int i : edge[x]) dfs(i, x);
    }
    else if (int(edge[x].size()) != 2) {
        for (int i : edge[x]) {
            if (i == p) continue;
            pc[i] = pc[x] ^ 1;
            dfs(i, x);
        }
    }
    else {
        ord[x] = ord[p] != -1 ? (ord[p] + 1) % 6 : (pc[x] ? 2 : 1);
        for (int i : edge[x]) {
            if (i == p) continue;
            pc[i] = "010011"[ord[x]] - '0';
            dfs(i, x);
        }
    }
}

vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
    for (int i = 0; i < m; ++i) {
        edge[U[i]].push_back(V[i]);
        edge[V[i]].push_back(U[i]);
    }
    if (A > 2) {
        vector<int> dist(n, -1);
        queue<int> q;
        q.push(0);
        dist[0] = 0;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i : edge[x]) {
                if (dist[i] != -1) continue;
                q.push(i);
                dist[i] = dist[x] + 1;
            }
        }
        vector<int> ret(m);
        for (int i = 0; i < m; ++i) {
            int u = U[i], v = V[i];
            if (dist[u] > dist[v]) swap(u, v);
            ret[i] = dist[u] % 3;
        }
        return ret;
    }
    dfs(0, -1);
    vector<int> ret(m);
    for (int i = 0; i < m; ++i) {
        int u = U[i], v = V[i];
        if (u == par[v]) swap(u, v);
        ret[i] = pc[u];
    }
    return ret;
}

Catherine

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

using namespace std;

static int A, B, pr;
static vector<int> path;

void Init(int a, int b) {
    A = a, B = b;
    pr = -1;
    path.clear();
}

int Move(vector<int> cnt) {
    if (A > 2) {
        int sum = 0;
        for (int i : cnt) sum += i > 0;
        if (sum == 1) {
            for (int i = 0; ; ++i) if (cnt[i]) return i;
        }
        else if (sum == 2) {
            for (int i = 0; ; ++i) if (!cnt[i]) return (i + 1) % 3;
        }
        else exit(1);
    }
    int deg = cnt[0] + cnt[1] + (pr != -1);
    if (deg != 2) path.resize(6);
    if (int(path.size()) > 5) {
        if (deg != 2 && pr != -1) ++cnt[pr];
        for (int i = 0; i < 2; ++i) {
            if (cnt[i] == 1) {
                if (pr != i) return pr = i;
                return -1;
            }
        }
        exit(2);
    }
    while (cnt[0]--) path.push_back(0);
    while (cnt[1]--) path.push_back(1);
    if (int(path.size()) == 5) {
        for (int i = 0; i < 6; ++i) {
            bool dif = 0;
            for (int j = 0; j < 5; ++j) {
                if (path[j] != "010011"[(i + j) % 6] - '0') dif = 1;
            }
            if (!dif) return path.push_back(0), -1;
        }
        path.push_back(path.back());
    }
    return pr = path.back();
}

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