oj.uz

Submission #516793

# Submission time Handle Problem Language Result Execution time Memory
516793 2022-01-22T06:32:22 Z jamezzz Stray Cat (JOI20_stray) C++17
15 / 100
 56 ms 21112 KB 
#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;
	}
}

#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 degree >=3
		if(pv==-1&&y[0]+y[1]>=3){
			found=true;
			return (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:1;
			else return (pv==0)?-1:0;
		}
		//if we know which way to go
		if(found)return (y[0]==1)?0:1;
		
		//first node
		if(pv==-1){
			//leaf node
			if(y[0]==0){
				found=true;
				return 1;
			}
			if(y[1]==0){
				found=true;
				return 0;
			}
			
			mask=1;
			++cnt;
			return 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 (y[0]==0)?1:0;
			}
		}
		
		return 0;
	}
}

Compilation message

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19852 KB Output is correct
2 Correct 3 ms 5288 KB Output is correct
3 Correct 32 ms 19204 KB Output is correct
4 Correct 49 ms 21112 KB Output is correct
5 Correct 49 ms 21016 KB Output is correct
6 Correct 40 ms 19672 KB Output is correct
7 Correct 40 ms 19732 KB Output is correct
8 Correct 51 ms 20468 KB Output is correct
9 Correct 44 ms 20448 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 19852 KB Output is correct
2 Correct 3 ms 5288 KB Output is correct
3 Correct 32 ms 19204 KB Output is correct
4 Correct 49 ms 21112 KB Output is correct
5 Correct 49 ms 21016 KB Output is correct
6 Correct 40 ms 19672 KB Output is correct
7 Correct 40 ms 19732 KB Output is correct
8 Correct 51 ms 20468 KB Output is correct
9 Correct 44 ms 20448 KB Output is correct
10 Correct 36 ms 17808 KB Output is correct
11 Correct 44 ms 17796 KB Output is correct
12 Correct 35 ms 17704 KB Output is correct
13 Correct 43 ms 17860 KB Output is correct
14 Correct 36 ms 18048 KB Output is correct
15 Correct 47 ms 18400 KB Output is correct
16 Correct 45 ms 20588 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17580 KB Output is correct
2 Correct 3 ms 5176 KB Output is correct
3 Correct 30 ms 16972 KB Output is correct
4 Correct 46 ms 18976 KB Output is correct
5 Correct 56 ms 18884 KB Output is correct
6 Correct 34 ms 17564 KB Output is correct
7 Correct 34 ms 17572 KB Output is correct
8 Correct 47 ms 18160 KB Output is correct
9 Correct 47 ms 18192 KB Output is correct
10 Correct 52 ms 17908 KB Output is correct
11 Correct 40 ms 17900 KB Output is correct
12 Correct 38 ms 17920 KB Output is correct
13 Correct 38 ms 18080 KB Output is correct
14 Correct 52 ms 18180 KB Output is correct
15 Correct 40 ms 18348 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17580 KB Output is correct
2 Correct 3 ms 5176 KB Output is correct
3 Correct 30 ms 16972 KB Output is correct
4 Correct 46 ms 18976 KB Output is correct
5 Correct 56 ms 18884 KB Output is correct
6 Correct 34 ms 17564 KB Output is correct
7 Correct 34 ms 17572 KB Output is correct
8 Correct 47 ms 18160 KB Output is correct
9 Correct 47 ms 18192 KB Output is correct
10 Correct 52 ms 17908 KB Output is correct
11 Correct 40 ms 17900 KB Output is correct
12 Correct 38 ms 17920 KB Output is correct
13 Correct 38 ms 18080 KB Output is correct
14 Correct 52 ms 18180 KB Output is correct
15 Correct 40 ms 18348 KB Output is correct
16 Correct 34 ms 15972 KB Output is correct
17 Correct 40 ms 15904 KB Output is correct
18 Correct 34 ms 16024 KB Output is correct
19 Correct 33 ms 15816 KB Output is correct
20 Correct 51 ms 16492 KB Output is correct
21 Correct 46 ms 16200 KB Output is correct
22 Correct 38 ms 18372 KB Output is correct
23 Correct 32 ms 15964 KB Output is correct
24 Correct 35 ms 15980 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5488 KB Output is correct
2 Correct 4 ms 5176 KB Output is correct
3 Correct 4 ms 5508 KB Output is correct
4 Correct 4 ms 5520 KB Output is correct
5 Correct 4 ms 5628 KB Output is correct
6 Correct 5 ms 5636 KB Output is correct
7 Incorrect 4 ms 5624 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 15732 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 15756 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -