Submission #1138314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138314		KhoaDuy	Stray Cat (JOI20_stray)	C++20	100 / 100	44 ms	13980 KiB

Anthony

#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> pat={0,1,0,0,1,1};
vector<vector<pair<int,int>>> graph;
void DFS(int u,int p,vector<int> &val,int last){
    if(graph[u].size()==2){
        for(pair<int,int> &x:graph[u]){
            int v=x.first,idx=x.second;
            if(v!=p){
                val[idx]=pat[(last+1)%pat.size()];
                DFS(v,u,val,(last+1)%pat.size());
            }
        }
    }
    else{
        for(pair<int,int> &x:graph[u]){
            int v=x.first,idx=x.second;
            if(v!=p){
                val[idx]=(pat[last]^1);
                DFS(v,u,val,val[idx]);
            }
        }
    }
}
vector<int> Mark(int n,int m,int a,int b,vector<int> e1,vector<int> e2){
    if(b==0){
        int dist[n];
        vector<vector<int>> adj(n);
        memset(dist,-1,sizeof(dist));
        dist[0]=0;
        queue<int> q;
        for(int i=0;i<m;i++){
            adj[e1[i]].push_back(e2[i]);
            adj[e2[i]].push_back(e1[i]);
        }
        q.push(0);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v:adj[u]){
                if(dist[v]==-1){
                    dist[v]=dist[u]+1;
                    q.push(v);
                }
            }
        }
        vector<int> val(m);
        for(int i=0;i<m;i++){
            val[i]=min(dist[e1[i]],dist[e2[i]]);
            val[i]%=3;
        }
        return val;
    }
    graph.clear();
    graph.resize(n);
    for(int i=0;i<m;i++){
        graph[e1[i]].push_back({e2[i],i});
        graph[e2[i]].push_back({e1[i],i});
    }
    vector<int> val(m);
    DFS(0,-1,val,5);
    return val;
}

Catherine

#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> pat={0,1,0,0,1,1};
int a,b;
int last=-1;
vector<int> seq;
bool know=false;
void Init(int A,int B){
    seq.clear();
    seq.resize(0);
    know=false;
    last=-1;
    a=A,b=B;
}
int Move(vector<int> y){
    if(b==0){
        int cnt=0,repre=-1;
        for(int i=0;i<a;i++){
            if(y[i]>0){
                cnt++;
                repre=i;
            }
        }
        if(cnt==1){
            return repre;
        }
        if(y[0]>0&&y[1]>0){
            return 0;
        }
        else if(y[1]>0&&y[2]>0){
            return 1;
        }
        else{
            return 2;
        }
    }
    int deg=(last!=-1);
    for(int i=0;i<a;i++){
        deg+=y[i];
    }
    if(deg==2){
        if(know){
            for(int i=0;i<a;i++){
                if(y[i]>0){
                    last=i;
                    return i;
                }
            }
        }
        for(int i=0;i<a;i++){
            for(int j=0;j<y[i];j++){
                seq.push_back(i);
            }
        }
        if(seq.size()==5){
            bool wrong=false;
            for(int i=0;i<pat.size();i++){
                bool flag=true;
                for(int j=0;j<seq.size();j++){
                    if(seq[j]!=pat[(i+j)%pat.size()]){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    wrong=true;
                    break;
                }
            }
            know=true;
            if(wrong){
                seq.clear();
                seq.resize(0);
                return -1;
            }
            last=seq.back();
            seq.clear();
            seq.resize(0);
            return last;
        }
        last=seq.back();
        return last;
    }
    else{
        if(last!=-1){
            y[last]++;
        }
        int Minidx=-1;
        for(int i=0;i<a;i++){
            if((Minidx==-1||y[i]<y[Minidx])&&y[i]>0){
                Minidx=i;
            }
        }
        know=true;
        if(last==Minidx){
            return -1;
        }
        last=Minidx;
        return Minidx;
    }
}

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