Submission #1281026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281026		Aviansh	Stray Cat (JOI20_stray)	C++20	100 / 100	57 ms	13972 KiB

Anthony

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

using namespace std;

namespace {
    void dfs(int st, vector<int>g[], int dep[], int par, int d, int val[], int len, int start){
        dep[st]=d;
        int v = (len+5)%6;
        if(v==1||v==2){
            if(start)
                val[st]=0;
            else{
                val[st]=1;
            }
        }
        else{
            val[st]=start;
        }
        int kid = 0;
        for(int i : g[st]){
            if(i==par)
                continue;
            kid++;
        }
        if(kid<=1){
            for(int i : g[st]){
                if(i==par)
                    continue;
                if(len==6){
                    len=0;
                    if(start){
                        start=0;
                    }
                    else{
                        start=1;
                    }
                }
                dfs(i,g,dep,st,d+1,val,len+1,start);
            }
        }
        else{
            for(int i : g[st]){
                if(i==par)
                    continue;
                if(val[st])
                    dfs(i,g,dep,st,d+1,val,1,0);
                else{
                    dfs(i,g,dep,st,d+1,val,1,1);
                }
            }
        }
    }
}  // namespace

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]);
    }
    if(a>=3){

        int dist[n];
        fill(dist,dist+n,1e9);
        priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
        pq.push({0,0});
        map<array<int,2>,int>col;
        while(!pq.empty()){
            array<int,2>tp = pq.top();
            pq.pop();
            if(tp[0]>=dist[tp[1]])
                continue;
            dist[tp[1]]=tp[0];
            for(int i : g[tp[1]]){
                if(col.find({tp[1],i})==col.end()){
                    col[{tp[1],i}]=tp[0]%3;
                    col[{i,tp[1]}]=tp[0]%3;
                }
                pq.push({tp[0]+1,i});
            }
        }
        vector<int>ans(m);
        for(int i = 0;i<m;i++){
            ans[i]=col[{u[i],v[i]}];
        }
        return ans;
    }

    assert(a==2);
    assert(m==n-1);
    int dep[n];
    int val[n];
    fill(val,val+n,-1);
    dfs(0,g,dep,-1,0,val,0,0);
    vector<int>ans(m);
    for(int i = 0;i<m;i++){
        if(dep[u[i]]>dep[v[i]]){
            ans[i]=val[u[i]];
        }
        else{
            ans[i]=val[v[i]];
        }
    }
    return ans;
}

Catherine

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

using namespace std;

namespace {

    int A, B;
    int ret;
    int las;
    string s;
    bool dirfound;
    bool valid(){
        set<string>pos;
        pos.insert("10011");
        pos.insert("00111");
        pos.insert("11101");
        pos.insert("10110");
        pos.insert("01100");
        pos.insert("11000");
        pos.insert("00010");
        pos.insert("01001");
        reverse(s.begin(),s.end());
        if(pos.find(s)!=pos.end()){
            reverse(s.begin(),s.end());
            return 1;
        }
        reverse(s.begin(),s.end());
        return 0;
    }

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    s="";
    dirfound=0;
    ret=0;
    las=-1;
}

int Move(vector<int> y) {

    if(A>=3){
        assert(min({y[0],y[1],y[2]})==0);
        if(y[2]==0){
            if(y[0]==0){
                return 1;
            }
            return 0;
        }
        else if(y[1]==0){
            if(y[2]==0){
                return 0;
            }
            return 2;
        }
        else{
            if(y[1]==0){
                return 2;
            }
            return 1;
        }
    }

    if(dirfound){
        if(y[0]==1&&y[1]!=1){
            las=0;
            return 0;
        }
        else if(y[0]!=1&&y[1]==1){
            las=1;
            return 1;
        }
        else{
            if(las){
                las=0;
                return las;
            }
            else{
                las=1;
                return las;
            }
        }
    }

    if(!dirfound){
        if(s.size()==0){
            if(y[0]==1&&y[1]!=1){
                dirfound=1;
                las=0;
                return 0;
            }
            else if(y[1]==1&&y[0]!=1){
                dirfound=1;
                las=1;
                return 1;
            }
            else{
                //sadge
                if(y[0]==0){
                    s+="11";
                    las=1;
                    return 1;
                }
                else if(y[1]==0){
                    s+="00";
                    las=0;
                    return 0;
                }
                else{
                    s+="10";
                    las=0;
                    return 0;
                }
            }
        }
        if(y[0]+y[1]>=2){
            //nice, good found
            if(las==1){
                y[1]++;
            }
            else if(las==0){
                y[0]++;
            }
            else{
                assert(0);
            }
            dirfound=1;
            if(y[0]==1){
                if(s[s.size()-1]=='0'){
                    las=0;
                    return -1;
                }
                las=0;
                return 0;
            }
            if(y[1]==1){
                if(s[s.size()-1]=='1'){
                    las=1;
                    return -1;
                }
                las=1;
                return 1;
            }
        }
        else{
            if(s.size()==5){
                //not corner case
                if(valid()){
                    dirfound=1;
                    if(y[0]==1){
                        las=0;
                        return 0;
                    }
                    else if(y[1]==1){
                        las=1;
                        return 1;
                    }
                    else{
                        assert(0);
                    }
                }
                else{
                    dirfound=1;
                    if(s[s.size()-1]=='0'){
                        las=0;
                    }
                    else{
                        las=1;
                    }
                    return -1;
                }
            }
            //sadge
            if(ret){
                ret--;
                if(ret==0){
                    if(y[0]==1){
                        s="0"+s;
                    }
                    else{
                        s="1"+s;
                    }
                    //found corner s
                    if(s[2]==s[3]){
                        if(s[0]==s[s.size()-1]){
                            //reverse direction
                            dirfound=1;
                            if(s[0]=='0'){
                                las=0;
                            }
                            else{
                                las=1;
                            }
                            return -1;
                        }
                        else{
                            dirfound=1;
                        }
                    }
                    else{
                        if(s[0]==s[s.size()-1]){
                            dirfound=1;
                        }
                        else{
                            //reverse direction
                            dirfound=1;
                            if(s[0]=='0'){
                                las=0;
                            }
                            else{
                                las=1;
                            }
                            return -1;
                        }
                    }
                }
                if(y[0]==1){
                    las=0;
                    return 0;
                }
                else if(y[1]==1){
                    las=1;
                    return 1;
                }
                else{
                    dirfound=1;
                    //assert(0);
                    return -1;
                }
            }
            if(y[0]==1){
                s+="0";
                if(s.size()==5){
                    //not corner case
                    if(valid()){
                        dirfound=1;
                        if(y[0]==1){
                            las=0;
                            return 0;
                        }
                        else{
                            las=1;
                            return 1;
                        }
                    }
                    else{
                        dirfound=1;
                        if(s[s.size()-1]=='0'){
                            las=0;
                        }
                        else{
                            las=1;
                        }
                        return -1;
                    }
                }
                if(s.size()==4){
                    //corner case
                    if(s[1]==s[3]){
                        ret=3;
                        if(s[s.size()-1]=='0'){
                            las=0;
                        }
                        else{
                            las=1;
                        }
                        return -1;
                    }
                }
                las=0;
                return 0;
            }
            else if(y[1]==1){
                s+="1";
                if(s.size()==5){
                    //not corner case
                    if(valid()){
                        dirfound=1;
                        if(y[0]==1){
                            las=0;
                            return 0;
                        }
                        else{
                            las=1;
                            return 1;
                        }
                    }
                    else{
                        dirfound=1;
                        if(s[s.size()-1]=='0'){
                            las=0;
                        }
                        else{
                            las=1;
                        }
                        return -1;
                    }
                }
                if(s.size()==4){
                    //corner case
                    if(s[1]==s[3]){
                        ret=3;
                        if(s[s.size()-1]=='0'){
                            las=0;
                        }
                        else{
                            las=1;
                        }
                        return -1;
                    }
                }
                las=1;
                return 1;
            }
            else{
                dirfound=1;
                if(s[s.size()-1]=='0'){
                    las=0;
                }
                else{
                    las=1;
                }
                return -1;
            }
        }
    }
    assert(0);
    return -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