oj.uz

Submission #516807

# Submission time Handle Problem Language Result Execution time Memory
516807 2022-01-22T06:53:16 Z jamezzz Stray Cat (JOI20_stray) C++17
20 / 100
 57 ms 20704 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 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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19548 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 31 ms 18972 KB Output is correct
4 Correct 47 ms 20704 KB Output is correct
5 Correct 47 ms 20684 KB Output is correct
6 Correct 36 ms 19288 KB Output is correct
7 Correct 48 ms 19380 KB Output is correct
8 Correct 45 ms 20072 KB Output is correct
9 Correct 44 ms 19976 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19548 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 31 ms 18972 KB Output is correct
4 Correct 47 ms 20704 KB Output is correct
5 Correct 47 ms 20684 KB Output is correct
6 Correct 36 ms 19288 KB Output is correct
7 Correct 48 ms 19380 KB Output is correct
8 Correct 45 ms 20072 KB Output is correct
9 Correct 44 ms 19976 KB Output is correct
10 Correct 35 ms 17512 KB Output is correct
11 Correct 41 ms 17428 KB Output is correct
12 Correct 34 ms 17452 KB Output is correct
13 Correct 35 ms 17428 KB Output is correct
14 Correct 34 ms 17644 KB Output is correct
15 Correct 40 ms 18068 KB Output is correct
16 Correct 46 ms 20184 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17236 KB Output is correct
2 Correct 2 ms 5232 KB Output is correct
3 Correct 30 ms 16624 KB Output is correct
4 Correct 57 ms 18404 KB Output is correct
5 Correct 44 ms 18496 KB Output is correct
6 Correct 34 ms 17244 KB Output is correct
7 Correct 35 ms 17252 KB Output is correct
8 Correct 42 ms 17736 KB Output is correct
9 Correct 42 ms 17796 KB Output is correct
10 Correct 39 ms 17532 KB Output is correct
11 Correct 38 ms 17496 KB Output is correct
12 Correct 45 ms 17504 KB Output is correct
13 Correct 39 ms 17536 KB Output is correct
14 Correct 45 ms 17884 KB Output is correct
15 Correct 40 ms 17840 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 17236 KB Output is correct
2 Correct 2 ms 5232 KB Output is correct
3 Correct 30 ms 16624 KB Output is correct
4 Correct 57 ms 18404 KB Output is correct
5 Correct 44 ms 18496 KB Output is correct
6 Correct 34 ms 17244 KB Output is correct
7 Correct 35 ms 17252 KB Output is correct
8 Correct 42 ms 17736 KB Output is correct
9 Correct 42 ms 17796 KB Output is correct
10 Correct 39 ms 17532 KB Output is correct
11 Correct 38 ms 17496 KB Output is correct
12 Correct 45 ms 17504 KB Output is correct
13 Correct 39 ms 17536 KB Output is correct
14 Correct 45 ms 17884 KB Output is correct
15 Correct 40 ms 17840 KB Output is correct
16 Correct 37 ms 15588 KB Output is correct
17 Correct 33 ms 15592 KB Output is correct
18 Correct 33 ms 15552 KB Output is correct
19 Correct 32 ms 15536 KB Output is correct
20 Correct 43 ms 16080 KB Output is correct
21 Correct 43 ms 15912 KB Output is correct
22 Correct 40 ms 17956 KB Output is correct
23 Correct 34 ms 15672 KB Output is correct
24 Correct 36 ms 15656 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5492 KB Output is correct
2 Correct 2 ms 5232 KB Output is correct
3 Correct 4 ms 5500 KB Output is correct
4 Correct 4 ms 5488 KB Output is correct
5 Correct 4 ms 5500 KB Output is correct
6 Correct 4 ms 5604 KB Output is correct
7 Correct 4 ms 5496 KB Output is correct
8 Correct 4 ms 5572 KB Output is correct
9 Correct 4 ms 5492 KB Output is correct
10 Correct 4 ms 5628 KB Output is correct
11 Correct 4 ms 5640 KB Output is correct
12 Correct 4 ms 5508 KB Output is correct
13 Correct 4 ms 5496 KB Output is correct
14 Correct 4 ms 5508 KB Output is correct
15 Correct 4 ms 5496 KB Output is correct
16 Correct 4 ms 5496 KB Output is correct
17 Correct 5 ms 5564 KB Output is correct
18 Correct 4 ms 5544 KB Output is correct
19 Correct 5 ms 5496 KB Output is correct
20 Correct 4 ms 5508 KB Output is correct
21 Correct 4 ms 5512 KB Output is correct
22 Correct 4 ms 5496 KB Output is correct
23 Correct 4 ms 5492 KB Output is correct
24 Correct 5 ms 5524 KB Output is correct
25 Correct 4 ms 5492 KB Output is correct
26 Correct 4 ms 5608 KB Output is correct
27 Correct 4 ms 5508 KB Output is correct
28 Correct 4 ms 5564 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15392 KB Output is correct
2 Correct 39 ms 16644 KB Output is correct
3 Correct 3 ms 5240 KB Output is correct
4 Correct 29 ms 15300 KB Output is correct
5 Correct 47 ms 18076 KB Output is correct
6 Correct 45 ms 18068 KB Output is correct
7 Incorrect 39 ms 17228 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15512 KB Output is correct
2 Correct 44 ms 16472 KB Output is correct
3 Correct 2 ms 5252 KB Output is correct
4 Correct 28 ms 15140 KB Output is correct
5 Correct 43 ms 18076 KB Output is correct
6 Incorrect 50 ms 18300 KB Wrong Answer [6]
7 Halted 0 ms 0 KB -