Submission #1135372

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

Anthony

#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace {
    vector <pair <int,int> > lab[20010];
    vector <int> asn;
    void dfs(int cur,int prv,int prvcol,int dep){
        if (!cur){
            for (pair <int,int> i:lab[cur]){
                asn[i.second]=0;
                dfs(i.first,cur,0,0);
            }
            return;
        }
        if (lab[cur].size()>=3){
            int nw=(prvcol^1);
            for (pair <int,int> i:lab[cur]){
                if (i.first==prv) continue;
                asn[i.second]=nw;
                dfs(i.first,cur,nw,nw);
            }
            return;
        }
        for (pair <int,int> i:lab[cur]){
            if (i.first==prv) continue;
            int nw=(dep+1)%6;
            if (nw==0||nw==2||nw==5) asn[i.second]=0;
            else asn[i.second]=1;
            dfs(i.first,cur,asn[i.second],nw);
        }
    }
}
vector <int> Mark(int N,int M,int A,int B,vector <int> U,vector <int> V){
    vector <int> g[N];
    for (int i=0; i<M; i++){
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
    }
    int dist[N];
    dist[0]=0;
    bool visited[N];
    for (int i=0; i<N; i++) visited[i]=0;
    visited[0]=1;
    queue <int> q;
    q.push(0);
    while (!q.empty()){
        int tp=q.front(); q.pop();
        for (int i:g[tp]){
            if (visited[i]) continue;
            visited[i]=1;
            q.push(i);
            dist[i]=dist[tp]+1;
        }
    }
    vector <int> ret(M);
    if (A>=3){
        for (int i=0; i<M; i++) ret[i]=min(dist[U[i]],dist[V[i]])%3;
    } else {
        for (int i=0; i<M; i++){
            lab[U[i]].push_back({V[i],i});
            lab[V[i]].push_back({U[i],i});
        }
        asn.resize(M);
        dfs(0,-1,0,0);
        ret=asn;
    }
    return ret;
}

Catherine

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

namespace {
int A,B,moves=0;
bool veri=0,bad=0;
int lst;
vector <int> trac;
}

void Init(int A, int B){
    ::A = A;
    ::B = B;
}
int Move(vector <int> y){
    if (A>=3){
        vector <int> hv;
        for (int i=0; i<A; i++){
            if (y[i]) hv.push_back(i);
        }
        if (hv.size()==1) return hv[0];
        for (int i=0; i<A; i++){
            if (!y[i]) return (i+1)%3;
        }
    }
    int sum=y[0]+y[1];
    moves++;
    if (moves==1&&sum>=3){
        veri=1;
        if (y[0]==1){
            trac.push_back(0);
            return 0;
        }
        trac.push_back(1);
        return 1;
    }
    if (bad){
        trac.pop_back();
        if (!trac.empty()) trac.pop_back();
        return -1;
    }
    if (moves>1&&sum>=2){
        if (!y[0]||!y[1]){
            bad=(trac.size()>1);
            lst=trac[0];
            trac.pop_back();
            return -1;
        }
        veri=1;
        trac.push_back(trac.back()^1);
        return trac.back();
    }
    if (veri){
        if (y[0]==1&&!y[1]){
            trac.push_back(0);
            return 0;
        }
        if (!y[0]&&y[1]==1){
            trac.push_back(1);
            return 1;
        }
        trac.push_back(trac.back()^1);
        return trac.back();
    }
    if (!sum){
        bad=(trac.size()>1);
        lst=trac[0];
        trac.pop_back();
        return -1;
    }
    if (trac.empty()){
        trac.push_back(lst^1);
        veri=1;
        return trac.back();
    }
    return 0;
}

• 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