Submission #516807

#	Time	Username	Problem	Language	Result	Execution time	Memory
516807		jamezzz	Stray Cat (JOI20_stray)	C++17	20 / 100	57 ms	20704 KiB

Anthony

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

int seq[6]={0,1,0,0,1,1};
vector<int> col,par,AL[200005];

void dfs(int u,int pv){
	if(AL[u].size()>2){
		for(int v:AL[u]){
			if(v==par[u])continue;
			col[v]=(seq[pv]==0)?1:0;
			par[v]=u;
			dfs(v,(seq[pv]==0)?1:0);
		}
	}
	else{
		for(int v:AL[u]){
			if(v==par[u])continue;
			col[v]=seq[(pv+1)%6];
			par[v]=u;
			dfs(v,(pv+1)%6);
		}
	}
}

vector<int> Mark(int N,int M,int A,int B,vector<int> U,vector<int> V){
	if(A>=3){
		vector<int> dist(N,-1);
		for(int i=0;i<M;++i){
			AL[U[i]].push_back(V[i]);
			AL[V[i]].push_back(U[i]);
		}
		queue<int> q;
		dist[0]=0;q.push(0);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int v:AL[u]){
				if(dist[v]==-1){
					dist[v]=dist[u]+1;
					q.push(v);
				}
			}
		}
		vector<int> X(M);
		for(int i=0;i<M;++i){
			if(dist[U[i]]!=dist[V[i]])X[i]=(dist[U[i]]+dist[V[i]])%3;
			else X[i]=(2*dist[U[i]]+1)%3;
		}
		return X;
	}
	else{
		col.resize(N);
		par.resize(N,-1);
		for(int i=0;i<M;++i){
			AL[U[i]].push_back(V[i]);
			AL[V[i]].push_back(U[i]);
		}
		dfs(0,5);
		vector<int> X(M);
		for(int i=0;i<M;++i){
			if(par[U[i]]==V[i])X[i]=col[U[i]];
			else X[i]=col[V[i]];
		}
		return X;
	}
}

Catherine

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

bool tree=true,found=false;
int mask,cnt;
int pv=-1;

int check[6]={25,18,5,11,22,12};

void Init(int A, int B){
	if(A>=3)tree=false;
}

int Move(vector<int> y){
	if(!tree){
		if(y[0]==0&&y[1]==0)return 2;
		if(y[0]==0&&y[2]==0)return 1;
		if(y[1]==0&&y[2]==0)return 0;
		if(y[0]==0)return 2;
		if(y[1]==0)return 0;
		if(y[2]==0)return 1;
	}
	else{
		//handle leaf
		if(y[0]==0&&y[1]==0)return -1;
		//handle degree >=3
		if(pv==-1&&y[0]+y[1]>=3){
			found=true;
			return pv=(y[0]>1)?1:0;
		}
		if(pv!=-1&&y[0]+y[1]>=2){
			found=true;
			if(y[0]+(pv==0)>1)return (pv==1)?-1:pv=1;
			else return (pv==0)?-1:pv=0;
		}
		//if we know which way to go
		if(found)return pv=(y[0]==1)?0:1;
		
		//first node
		if(pv==-1){
			//leaf node
			if(y[0]==0){
				found=true;
				return pv=1;
			}
			if(y[1]==0){
				found=true;
				return pv=0;
			}
			
			mask=1;
			++cnt;
			return pv=1;
		}
		else{
			//reached a leaf
			if(y[0]==0&&y[1]==0){
				found=true;
				return -1;
			}
			mask<<=1;
			if(y[0]==0)++mask;
			if(cnt==3){
				bool in=false;
				for(int i=0;i<6;++i){
					if(mask==check[i])in=true;
				}
				found=true;
				if(in)return (y[0]==0)?1:0;
				else return -1;
			}
			else{
				++cnt;
				return pv=(y[0]==0)?1:0;
			}
		}
		
		return pv=0;
	}
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:81:1: warning: control reaches end of non-void function [-Wreturn-type]
   81 | }
      | ^

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