Submission #1000682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000682		Unforgettablepl	Stray Cat (JOI20_stray)	C++17	15 / 100	37 ms	16776 KiB

Anthony

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

namespace {


vector<int> strat1(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    // General Graph A=3
    vector<int> ans(M,-1);
    vector<vector<pair<int,int>>> adj(N);
    for(int i=0;i<M;i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    vector<bool> visited(N);
    queue<pair<int,int>> q;
    q.emplace(0,0);
    while(!q.empty()){
        auto [idx,col] = q.front();q.pop();
        if(visited[idx])continue;
        visited[idx]=true;
        for(auto&i:adj[idx]){
            if(ans[i.second]==-1)ans[i.second]=col;
            if(!visited[i.first])q.emplace(i.first,(col+1)%3);
        }
    }
    return ans;
}


vector<bool> magic = {1,1,0,0,1,0};
vector<vector<pair<int,int>>> adj;
vector<bool> ans;

void dfs(int x,int p,bool parcol,int seqidx){
    if(adj[x].size()==1)return;
    if(adj[x].size()==2){
        // Colour using sequence
        seqidx = (seqidx+1)%6;
        if(adj[x][0].first==p)swap(adj[x][0],adj[x][1]);
        if(magic[seqidx]){
            ans[adj[x][0].second]=true;
            dfs(adj[x][0].first,x,true,seqidx);
        } else {
            dfs(adj[x][0].first,x,false,seqidx);
        }
        return;
    }
    // Colour using b&w
    for(auto&i:adj[x])if(i.first!=p){
        if(parcol){
            dfs(i.first,x,false,2);
        } else {
            ans[i.second]=true;
            dfs(i.first,x,true,0);
        }
    }
}

vector<int> strat2(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    // Tree A=2,B=6
    adj = vector<vector<pair<int,int>>>(N);
    ans = vector<bool>(M);
    for(int i=0;i<M;i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    for(auto&i:adj[0]){
        dfs(i.first,0,false,2);
    }
    vector<int> col(M);
    for(int i=0;i<M;i++)if(ans[i])col[i]=1;
    return col;
}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    if(A>=3)return strat1(N,M,A,B,U,V);
    else return strat2(N,M,A,B,U,V);
}

Catherine

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

namespace {

int A, B;
int strat1(vector<int> y) {
    // General Graph A=3
    bool more0 = y[0]>0;
    bool more1 = y[1]>0;
    bool more2 = y[2]>0;
    if(more0 and more1)return 0;
    if(more1 and more2)return 1;
    if(more2 and more0)return 2;
    if(more0)return 0;
    if(more1)return 1;
    if(more2)return 2;
    assert(false);
}

vector<bool> magic = {1,1,0,0,1,0};

vector<vector<int>> good = {
    {0,1,1,0,0},
    {1,0,1,1,0},
    {0,1,0,1,1},
    {0,0,1,0,1},
    {1,0,0,1,0},
    {1,1,0,0,1},
};

// False phase is detection phase
// True phase is travelling phase
bool phase = false;
int lastmov = -1;

vector<int> currseq;

int strat2(vector<int> y) {
    // Tree A=2,B=6
    if(phase){
        if(y[0]==1)return 0;
        return 1;
    }
    if(y[0]==0 and y[1]==0){
        // We are at a leaf
        phase = true;
        return -1;
    }
    // Emplace current situation into sequence
    if(lastmov==-1){
        if(y[0]+y[1]>2){ // Non-line node
            phase = true;
            return strat2(y);
        }
        if(y[0]==2){
            currseq = {0,0};
            lastmov = 0;
            return 0;
        } else if(y[1]==2){
            currseq = {1,1};
            lastmov = 1;
            return 1;
        } else {
            currseq = {0,1};
            lastmov = 1;
            return 1;
        }
    } else {
        if(y[0]+y[1]>=2){ // Non-line node
            y[lastmov]++;
            phase = true;
            if(y[0]==1)return 0;
            else return 1;
        }
        if(y[0]==1){
            currseq.emplace_back(0);
            if(currseq.size()!=5){
                lastmov = 0;
                return 0;
            }
        } else {
            currseq.emplace_back(1);
            if(currseq.size()!=5){
                lastmov = 1;
                return 1;
            }
        }
    }
    if(currseq.size()==5){
        phase = true;
        if(find(good.begin(),good.end(),currseq)==good.end())return strat2(y);
        else return -1;
    }
    assert(false);
}

}  // namespace

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

int Move(vector<int> y) {
    if(A>=3)return strat1(y);
    else return strat2(y);
}

• 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