Submission #1081485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081485		isaachew	Stray Cat (JOI20_stray)	C++17	100 / 100	60 ms	19620 KiB

Anthony

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

namespace {
std::vector<std::vector<int>> edges;
std::map<std::pair<int,int>,int> eids;
std::vector<int> marks;
std::vector<int> visited;
void dfs(int cur,int parent,int prog){
    if(visited[cur]){
        marks[eids[{cur,parent}]]=2;
        return;
    }
    visited[cur]=1;
    if(cur!=0)marks[eids[{cur,parent}]]=(13>>(prog%6))&1;
    int oldm=(13>>(prog%6))&1;
    int nprog=edges[cur].size()==2?prog+1:oldm?4:0;
    for(int i:edges[cur]){
        if(i==parent)continue;
        dfs(i,cur,nprog);
    }
}
}  // namespace
/*
 DFS tree?
 101100 away from node 0
 001101 along the branches of the tree - if you are going the wrong way, it will be reversed
 
 
 001101
 
 01100
 11001
 10010
 00101
 01011
 10110
 all appear only in reverse
 
 If you see one of the rotations of it, go back the other way
 
 */
std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    marks.resize(M);
    edges.resize(N);
    visited.resize(N);
    for(int i=0;i<M;i++){
        eids[{U[i],V[i]}]=i;
        eids[{V[i],U[i]}]=i;
        edges[U[i]].push_back(V[i]);
        edges[V[i]].push_back(U[i]);
    }
    if(A==2){
        dfs(0,0,0);
    }else{
        std::queue<std::pair<int,int>> bfs;
        std::vector<int> dists(N,-1);
        bfs.push({0,0});
        while(!bfs.empty()){
            std::pair<int,int> cur=bfs.front();
            bfs.pop();
            if(dists[cur.first]!=-1)continue;
            dists[cur.first]=cur.second;
            for(int i:edges[cur.first]){
                if(dists[i]==-1){
                    marks[eids[{cur.first,i}]]=cur.second%3;
                    bfs.push({i,cur.second+1});
                }
            }
        }
    }
    //for(int i:marks)std::cout<<i<<'\n';
  return marks;
}

Catherine

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

namespace {
int tree=0;
int num=0;
int last6=-1;
int last=0;
}  // namespace
/*
 001101
 */
void Init(int A, int B) {
    if(A==2)tree=1;
}

int Move(std::vector<int> y) {
    
    /*
     std::cout<<"move "<<last<<'\n';
    std::cout<<last6<<'\n';
    std::cout<<"seen\n";
    for(int i:y){
        std::cout<<i<<' ';
    }
    std::cout<<'\n';
     */
    if(tree){
        if(num==0){
            if(y[0]+y[1]==2){
                if(y[1]==0){
                    last6=0;
                    last=0;
                }else if(y[1]==1){
                    last6=1;
                    last=1;
                }else if(y[1]==2){
                    last6=3;
                    last=1;
                }
                num=2;
                return last;//don't care
            }else{
                num=-1e9;
                last=y[1]==1;
                return last;//what appears once
            }
        }
        if(y[0]+y[1]>=2){
            num=-1e9;
            int n=y[1];
            int move;
            if(y[0]==0||y[1]==0)move=-1;
            else if((y[0]+!last)==1)move=0;
            else move=1;
            last=move==-1?last:move;
            return move;
        }else if(y[0]+y[1]==1){
            last6<<=1;last6+=y[1];num++;
            if(num==5){
                if(last6==12||last6==25||last6==18||last6==5||last6==11||last6==22){
                    num=-1e9;
                    last=last;
                    return -1;
                }
            }
            last=y[1];
            return last;
        }else{
            num=-1e9;last=last;
            return -1;
        }
    }else{
        if(y[2]==0&&y[0]!=0)return 0;
        if(y[0]==0&&y[1]!=0)return 1;
        if(y[1]==0&&y[2]!=0)return 2;
        return 12345;
    }
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:51:17: warning: unused variable 'n' [-Wunused-variable]
   51 |             int n=y[1];
      |                 ^

• 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