Submission #565996

#	Time	Username	Problem	Language	Result	Execution time	Memory
565996		InternetPerson10	Stray Cat (JOI20_stray)	C++17	5 / 100	53 ms	15708 KiB

Anthony

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

using namespace std;

#include <vector>

namespace {

    // orig: 1 1 0 1 0 0
vector<int> sixchain = {1, 1, 0, 1, 0, 0};
vector<vector<pair<int, int>>> adj;
vector<int> marks, chain;

struct dsu {
    vector<int> par, siz;
    dsu(int n) {
        par.resize(n);
        siz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x); y = get(y);
        if(x == y) return false;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

void dfs(int n, int par = -1, int na = -1, int ne = -1) {
    if(na != -1) {
        if(adj[par].size() == 2) {
            chain[n] = (chain[par] + 1) % 6;
            if(ne == -1) marks[na] = 0;
            else marks[na] = sixchain[chain[n]];
        }
        else {
            chain[n] = -1;
            if(ne == -1) marks[na] = 0;
            else marks[na] = (1 + marks[ne]) % 2;
        }
    }
    for(auto p : adj[n]) {
        int ch, nu;
        tie(ch, nu) = p;
        if(ch == par) continue;
        dfs(ch, n, nu, na);
    }
}

}  // namespace

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    marks.resize(M, 0);
    chain.resize(N, 0);
    adj.resize(N);
    if(M != N - 1) {
        dsu uf(N);
        vector<int> v1, v2;
        for(int i = 0; i < M; i++) {
            if(!uf.unite(U[i], V[i])) {
                U[i] = V[i] = -1;
                marks[i] = 2;
            }
        }
    }
    for(int i = 0; i < M; i++) {
        if(U[i] == -1) continue;
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    dfs(0);
    return marks;
}

Catherine

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

using namespace std;

namespace {

vector<int> sixchain = {1, 1, 0, 1, 0, 0};
vector<vector<pair<int, int>>> adj;
vector<int> marks, chain;

struct dsu {
    vector<int> par, siz;
    dsu(int n) {
        par.resize(n);
        siz.resize(n, 1);
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int get(int x) {
        if(par[x] == x) return x;
        return par[x] = get(par[x]);
    }
    bool unite(int x, int y) {
        x = get(x); y = get(y);
        if(x == y) return false;
        if(siz[x] > siz[y]) swap(x, y);
        par[x] = y;
        siz[y] += siz[x];
        return true;
    }
};

void dfs(int n, int par = -1, int na = -1) {
    if(na != -1) {
        if(adj[par].size() == 2) {
            chain[n] = (chain[par] + 1) % 6;
            marks[na] = (sixchain[chain[n]] + chain[par]) % 2;
        }
        else {
            chain[n] = -1;
            marks[na] = (1 + chain[par]) % 2;
        }
    }
    for(auto p : adj[n]) {
        int ch, nu;
        tie(ch, nu) = p;
        if(ch == par) continue;
        dfs(ch, n, nu);
    }
}

vector<int> marksGot;
int goBack = -1;
int goUp = 0;

set<vector<int>> goingDown = {
    {1, 1, 0, 1, 0, 0},
    {1, 0, 1, 0, 0, 1},
    {0, 1, 0, 0, 1, 1},
    {1, 0, 0, 1, 1, 0},
    {0, 0, 1, 1, 0, 1},
    {0, 1, 1, 0, 1, 0}
};

}  // namespace

void Init(int A, int B) {
}

vector<int> y;

int findVal(int x) {
    marksGot.push_back(x);
    return x;
}

int Move(std::vector<int> k) {
    y = k;
    int ySize = y[0] + y[1], mini = 2;
    if(y[0]) mini = 0;
    else mini = 1;
    if(marksGot.size() == 0) {
        if(ySize == 1) {
            goUp = 1;
            return findVal(mini);
        }
        if(ySize == 2) {
            return findVal(mini);
        }
        goUp = 1;
        if(y[0] == 1) return findVal(0);
        return findVal(1);
    }
    if(goBack > -1) {
        goBack--;
        if(goBack == -1) goUp = 1;
        return findVal(mini);
    }
    if(goUp) {
        if(ySize == 1) {
            return findVal(mini);
        }
        int x = marksGot.back();
        return findVal(1-x);
    }
    if(ySize == 0) { // Reached leaf
        marksGot.push_back(marksGot.back());
        goBack = marksGot.size();
        return -1;
    }
    if(ySize == 1 && marksGot.size() < 6) {
        return findVal(mini);
    }
    if(ySize == 1 && marksGot.size() == 6) {
        if(goingDown.count(marksGot)) {
            goBack = 4;
            marksGot.push_back(marksGot[5]);
            return -1;
        }
        else { // Going up na pala
            goUp = 1;
            return findVal(mini);
        }
    }
    if(ySize > 1) {
        goUp = 1;
        if(y[0] == 0) {
            marksGot.push_back(1);
            return -1;
        }
        if(y[1] == 0) {
            marksGot.push_back(0);
            return -1;
        }
        return findVal(1-marksGot.back());
    }
    while(true) {}
    assert(false);
}

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