Submission #1139342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139342		nathan4690	Stray Cat (JOI20_stray)	C++20	15 / 100	31 ms	13896 KiB

Anthony

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

namespace {
}  // namespace

vector<int> Mark(int N, int M, int A, int B,
                      vector<int> U, vector<int> V) {
    vector<pair<int,int>> G[N];
    for(int i=0;i<M;i++){
        int u = U[i], v = V[i];
        G[u].push_back({v, i});
        G[v].push_back({u, i});
    }
    vector<int> res(M), col(N);
    vector<int> vis(N, 0);
    queue<int> qu;
    if(A > 2){
        qu.push(0);
        vis[0] = 1; col[0] = 0;
        while(!qu.empty()){
            int u = qu.front();
            qu.pop();
            vis[u] = 2;
            for(pair<int,int> e: G[u]){
                int c = e.first, idx = e.second;
                if(vis[c] == 0){
                    qu.push(c);
                    vis[c] = 1;
                    col[c] = (col[u] + 1) % 3;
                }
                if(vis[c] != 2){
                    res[idx] = col[u];
                }
            }
        }
        return res;
    }
    vector<int> par(N);
    qu.push(0);
    vis[0] = 1;
    while(!qu.empty()){
        int u = qu.front();
        qu.pop();
        vis[u] = 1;
        for(pair<int,int> e: G[u]){
            int c = e.first, idx = e.second;
            if(vis[c]) continue;
            par[c] = u;
            qu.push(c);
            int deg = G[u].size() - (u != 0);
            if(G[c].size() == 2){
                if(deg == 1){
                    col[c] = (col[u] + 1) % 6;
                }else{
                    col[c] = (col[u] == 1 ? 2 : 1);
                }
            }else{
                if(deg == 1){
                    int rcol = "010011"[col[u]] - '0';
                    col[c] = 1 - rcol;
                }else{
                    col[c] = (col[u] + 1) % 2;
                }
            }
        }
    }
    for(int u=0;u<N;u++){
        for(pair<int,int> c: G[u]){
            int v = c.first, idx = c.second;
            if(v == par[u]) continue;
            int deg = G[u].size() - (u != 0);
            if(deg == 1){
                res[idx] = "010011"[col[u]] - '0';
            }else{
                res[idx] = col[u];
            }
        }
    }
    return res;
}

Catherine

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

namespace {

int A, B;
string passed;
bool ok = false;

}  // namespace

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

int Move(std::vector<int> y) {
    if(A > 2){
        if(y[0] && y[1]) return 0;
        if(y[1] && y[2]) return 1;
        if(y[0] && y[2]) return 2;
        if(y[0]) return 0;
        if(y[1]) return 1;
        if(y[2]) return 2;
    }
    int deg = accumulate(y.begin(), y.end(), (int)(passed.size() > 0));
    if(deg == 1){
        ok = true;
        bool isemp = passed.empty();
        if(isemp) {
            passed += char((int)(max_element(y.begin(), y.end()) - y.begin()));
        }
        return (isemp ? (int)(max_element(y.begin(), y.end()) - y.begin()) : -1);
    }
    vector<int> all;
    for(int i=0;i<y[0];i++) all.push_back(0);
    for(int i=0;i<y[1];i++) all.push_back(1);
    if(deg == 2){
        if(ok) {
            int rr = (int)(max_element(y.begin(), y.end()) - y.begin());
            passed += char(rr + '0');
            return rr;
        }
        if(passed.empty()){
            passed += char('0' + all[0]);
            passed += char('0' + all[1]);
            return all[1];
        }
        passed += all[0];
        if(passed.size() == 5){
            ok = true;
            if(passed == "01001" || passed == "10011" || passed == "00110" || passed == "01101" || passed == "11010" || passed == "10100"){
                passed.pop_back();
                return -1;
            }
        }
        return all[0];
    }
    ok = true;
    y[passed.back() - '0']++;
    int go = (int)(find(y.begin(), y.end(), 1) - y.begin());
//    y[go] = 0;
//    go = (int)(max_element(y.begin(), y.end()) - y.begin());
    if((!passed.empty()) && passed.back() - '0' == go) return -1;
    passed += char('0' + go);
    return go;
}

• 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