oj.uz

Submission #516805

# Submission time Handle Problem Language Result Execution time Memory
516805 2022-01-22T06:47:19 Z jamezzz Stray Cat (JOI20_stray) C++17
15 / 100
 62 ms 20712 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 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

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 43 ms 19476 KB Output is correct
2 Correct 3 ms 5232 KB Output is correct
3 Correct 44 ms 18904 KB Output is correct
4 Correct 49 ms 20676 KB Output is correct
5 Correct 46 ms 20712 KB Output is correct
6 Correct 39 ms 19240 KB Output is correct
7 Correct 40 ms 19284 KB Output is correct
8 Correct 42 ms 20100 KB Output is correct
9 Correct 46 ms 20080 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 19476 KB Output is correct
2 Correct 3 ms 5232 KB Output is correct
3 Correct 44 ms 18904 KB Output is correct
4 Correct 49 ms 20676 KB Output is correct
5 Correct 46 ms 20712 KB Output is correct
6 Correct 39 ms 19240 KB Output is correct
7 Correct 40 ms 19284 KB Output is correct
8 Correct 42 ms 20100 KB Output is correct
9 Correct 46 ms 20080 KB Output is correct
10 Correct 37 ms 17440 KB Output is correct
11 Correct 39 ms 17376 KB Output is correct
12 Correct 34 ms 17488 KB Output is correct
13 Correct 36 ms 17284 KB Output is correct
14 Correct 34 ms 17728 KB Output is correct
15 Correct 51 ms 17972 KB Output is correct
16 Correct 47 ms 20244 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17068 KB Output is correct
2 Correct 3 ms 5184 KB Output is correct
3 Correct 29 ms 16820 KB Output is correct
4 Correct 62 ms 18524 KB Output is correct
5 Correct 44 ms 18488 KB Output is correct
6 Correct 34 ms 17092 KB Output is correct
7 Correct 34 ms 17136 KB Output is correct
8 Correct 42 ms 17760 KB Output is correct
9 Correct 47 ms 17888 KB Output is correct
10 Correct 41 ms 17484 KB Output is correct
11 Correct 40 ms 17436 KB Output is correct
12 Correct 40 ms 17520 KB Output is correct
13 Correct 40 ms 17468 KB Output is correct
14 Correct 59 ms 17832 KB Output is correct
15 Correct 42 ms 17820 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 17068 KB Output is correct
2 Correct 3 ms 5184 KB Output is correct
3 Correct 29 ms 16820 KB Output is correct
4 Correct 62 ms 18524 KB Output is correct
5 Correct 44 ms 18488 KB Output is correct
6 Correct 34 ms 17092 KB Output is correct
7 Correct 34 ms 17136 KB Output is correct
8 Correct 42 ms 17760 KB Output is correct
9 Correct 47 ms 17888 KB Output is correct
10 Correct 41 ms 17484 KB Output is correct
11 Correct 40 ms 17436 KB Output is correct
12 Correct 40 ms 17520 KB Output is correct
13 Correct 40 ms 17468 KB Output is correct
14 Correct 59 ms 17832 KB Output is correct
15 Correct 42 ms 17820 KB Output is correct
16 Correct 31 ms 15644 KB Output is correct
17 Correct 39 ms 15716 KB Output is correct
18 Correct 38 ms 15424 KB Output is correct
19 Correct 36 ms 15564 KB Output is correct
20 Correct 47 ms 16132 KB Output is correct
21 Correct 35 ms 15788 KB Output is correct
22 Correct 39 ms 18008 KB Output is correct
23 Correct 39 ms 15752 KB Output is correct
24 Correct 33 ms 15584 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5496 KB Output is correct
2 Correct 4 ms 5352 KB Output is correct
3 Correct 5 ms 5492 KB Output is correct
4 Correct 4 ms 5548 KB Output is correct
5 Correct 4 ms 5500 KB Output is correct
6 Correct 4 ms 5492 KB Output is correct
7 Incorrect 4 ms 5500 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15304 KB Output is correct
2 Correct 53 ms 16996 KB Output is correct
3 Correct 3 ms 5284 KB Output is correct
4 Correct 28 ms 15532 KB Output is correct
5 Correct 45 ms 18492 KB Output is correct
6 Correct 47 ms 18608 KB Output is correct
7 Incorrect 33 ms 17592 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15508 KB Output is correct
2 Correct 38 ms 16820 KB Output is correct
3 Correct 3 ms 5240 KB Output is correct
4 Correct 35 ms 15628 KB Output is correct
5 Correct 48 ms 18524 KB Output is correct
6 Correct 45 ms 18556 KB Output is correct
7 Correct 35 ms 17664 KB Output is correct
8 Correct 43 ms 17676 KB Output is correct
9 Correct 44 ms 18600 KB Output is correct
10 Correct 54 ms 18492 KB Output is correct
11 Correct 44 ms 18448 KB Output is correct
12 Correct 43 ms 18460 KB Output is correct
13 Incorrect 41 ms 17608 KB Wrong Answer [5]
14 Halted 0 ms 0 KB -