Submission #710457

#	Time	Username	Problem	Language	Result	Execution time	Memory
710457		zyq_	Stray Cat (JOI20_stray)	C++17	0 / 100	46 ms	20248 KiB

Anthony

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

vector<pair<int, int> > adjList[200010];
int lonecnt[200010];
int ans[200010];

int lonecolour[] = {0, 1, 1, 0, 0, 1};

void dfs(int x, int dist, int parent = -1){ //ret val is lone seg count
    for(auto it: adjList[x]){
        if(it.first == parent) continue;
        if((x==0 && (int)adjList[x].size()==1)||(x!=0&&(int)adjList[x].size()==2)){
            if(lonecnt[x] != 0){
                lonecnt[it.first] = lonecnt[x]+1;
            }
            else{
                if(dist % 2 == 0){
                    lonecnt[it.first] = 1;
                }
                else{
                    lonecnt[it.first] = 0;
                }
            }
        }
        dfs(it.first, dist+1, x);
    }
}
//weve got the lonecnt time to colour some stuff

void colouring(int x, int prev, int parent = -1){
    for(auto it: adjList[x]){
        if(it.first == parent) continue;
        //start to colour from 0
        if(lonecnt[it.first] == 0){
            ans[it.second] = (prev+1)%2;
        }
        else{
            ans[it.second] = lonecolour[(lonecnt[it.first]-1)%6];
        }
        colouring(it.first, ans[it.second], x);
    }
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V){
    //look for lone segments
    for(int a=0; a<M; a++){
        adjList[U[a]].push_back({V[a], a});
        adjList[V[a]].push_back({U[a], a});
    }
    dfs(0, 0);
    colouring(0, 1);
    vector<int> ret;
    for(int a=0; a<M; a++) ret.push_back(ans[a]);
    return ret;
}

Catherine

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

bool resolved;
int prev1, prev2, prev3, prev4, prev5, prev6;

void Init(int A, int B){
    resolved = false;
    prev1 = prev2 = prev3 = prev4 = prev5 = prev6 = -1;
}

int Move(vector<int> y){
    //check LOL
    if(resolved){
        //keep moving in different
        if(prev1 == 0){
            prev1 = 1;
            return 1;
        }
        else{
            prev1 = 0;
            return 0;
        }
    }
    else{
        //check if current place is good ?
        if(prev1 == -1){
            //first step
            if(y[1] >= 1){
                prev1 = 1;
                return 1;
            }
            else{
                prev1 = 0;
                return 0;
            }
        }
        if(y[0] + y[1] == 0){
            resolved = true;
            return -1;
        }
        if(y[1] + y[0] > 1){
            if(y[prev1] == 0){
                resolved = true;
                return -1;
            }
            else{
                prev1 = (prev1 + 1)%2;
                return prev1;
            }
        }
        //now is when on lone
        //start moving
        else{
            //not first step
            prev6 = prev5;
            prev5 = prev4;
            prev4 = prev3;
            prev3 = prev2;
            prev2 = prev1;
            //look at prev2
            if(y[0] == 1){
                prev1 = 0;
            }
            else if(y[1] == 1){
                prev1 = 1;
            }
            if(prev1 != prev2 && prev3 == prev4 && prev3 != -1){
                resolved = true;
                if(prev3 == 0){
                    //rightdirectoin
                    return prev1;
                }
                else{
                    return -1;
                }
            }
            else{
                return prev1;
            }
        }
    }
}

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