Submission #1166994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166994		egregious	Stray Cat (JOI20_stray)	C++20	4 / 100	31 ms	13896 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    vector<vector<int>> g(N);
    for (int i = 0; i < M; i++) {
        g[U[i]].push_back(i);
        g[V[i]].push_back(i);
    }
    vector<int> a;
    if (A > 2) a = {0, 1, 2};
    else a = {0, 1, 0, 0, 1, 1};
    vector<int> idx(N, -1), X(M, -1);
    queue<int> bfs;
    bfs.push(idx[0] = 0);
    while (bfs.size()) {
        int x = bfs.front();
        bfs.pop();
        for (int y : g[x]) {
            if (X[y] < 0) X[y] = a[idx[x]];
            int z = U[y] ^ V[y] ^ x;
            if (idx[z] < 0) {
                if (g[y].size() > 2 && A == 2) idx[z] = !a[idx[x]];
                else idx[z] = (idx[x] + 1) % a.size();
                bfs.push(z);
            }
        }
    }
    // for (int i = 0; i < N; i++) {
    //     cout << i << ": ";
    //     for (int j : g[i]) cout << X[j] << " ";
    //     cout << endl;
    // }
    return X;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
    int A, B, lst = -1;
    bool amb = true; // whether direction is currently ambiguous
    string signs = "";
    string ord = "010011010011";
}

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

int Move(vector<int> y) {
    if (A > 2) {
        if (!y[0]) return y[1] ? 1 : 2;
        if (!y[1]) return y[2] ? 2 : 0;
        if (!y[2]) return y[0] ? 0 : 1;
        // assert(false); // we should never reach here
    }
    int opt = accumulate(y.begin(), y.end(), 0) + (lst >= 0);
    if (opt > 2) { // at junction
        amb = false;
        return lst = (y[1] + max(lst, 0) == 1); // pick mark which only has one road---since deg > 2, this is unique
    }
    else if (opt == 1) { // at leaf
        amb = false;
        if (lst >= 0) return -1;
        return lst = y[1];
    }
    else if (!amb) { // at deg 2 node, direction known
        return lst = y[1]; // just pick the one edge which is not the one we just traversed
    }
    else { // at deg 2 node, direction still ambiguous
        for (int _ = 0; _ < y[0]; _++) signs.push_back('0');
        for (int _ = 0; _ < y[1]; _++) signs.push_back('1');
        if (signs.size() == 5) { // now we can decide whether we're going in the right direction
            amb = false;
            for (int i = 0; i < 6; i++) if (signs == ord.substr(i, 5)) return -1;
        }
        if (y[0] && y[1]) return lst = 1;
        return lst = y[1];
    }
}

• 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