oj.uz

Submission #217461

# Submission time Handle Problem Language Result Execution time Memory
217461 2020-03-29T19:20:13 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1071 ms 18496 KB 
#include "Anthony.h"
#define MAXN 20007
#include <bits/stdc++.h>

namespace {
	int a,b;
	int d[MAXN],nz[6]={0,1,0,0,1,1};
	std::vector<int> g[MAXN],ind[MAXN],X;
	void dfs(int s,int f,int a)
	{
		if(g[s].size() + (s==0) ==2) {for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) {X[ind[s][i]]=nz[a]; dfs(g[s][i],s,(a+1)%6);}}
		else for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) {X[ind[s][i]]=nz[a]; dfs(g[s][i],s,1-nz[a]);}
	}
}

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) 
{
	for(int i=0;i<M;i++) X.push_back(0);
	a=A;
	for(int i=0;i<M;i++) g[U[i]].push_back(V[i]);
	for(int i=0;i<M;i++) ind[U[i]].push_back(i);
	for(int i=0;i<M;i++) g[V[i]].push_back(U[i]);
	for(int i=0;i<M;i++) ind[V[i]].push_back(i);
	if(a>=3)
  	{
  		d[0]=0;
  		std::fill(d+1,d+N,-1);
  		std::queue<int> q;
  		q.push(0);
		while(!q.empty())
  		{
  			int u=q.front();
			q.pop();
  			for(int i=0;i<g[u].size();i++) if(d[g[u][i]]==-1)
  			{
  				d[g[u][i]]=d[u]+1;
  				q.push(g[u][i]);
			}		
		for(int i=0;i<M;i++) X[i]=std::min(d[U[i]],d[V[i]])%3;
		}
	}
	else dfs(0,0,0);
	return X;
}
#include "Catherine.h"
#include <bits/stdc++.h>

namespace {

	int a, b,br,nz[6]={0,1,0,0,1,1},pr;
	bool sig=false;
	std::vector<int> vd;
} 

void Init(int A, int B) {
  	a = A;
  	b = B;
}

int Move(std::vector<int> y) {
  	if(a>=3) {for(int i=0;i<3;i++) if(y[i]==0 && y[(i+1)%3]!=0) return (i+1)%3;}
  	else
  	{
  		br++;
  		int deg=y[0]+y[1]+(br!=1);
		if(sig) 
		{
			if(deg>=3)
			{
				pr=1-pr; 
				return pr;
			}
			if(y[0]!=0) return 0;
			return 1;
		}
		if(deg==1) 
		{
			sig=true;
			if(br!=1) return -1;
			if(y[0]!=0) return 0;
			return 1; 
		}
		if(deg>2)
		{
			y[pr]++;
			sig=true;
			if(y[0]==1) {pr=0; return 0;}
			if(y[1]==1) {pr=1; return 1;}
		}
		if(br<=3) 
		{
			if(y[0]!=0) pr=0;
			else pr=1;
			if(br==1) vd.push_back(y[1]-pr);
			vd.push_back(pr);
			return pr;
		}
		if(br==4)
		{
			int op;
			if(y[0]!=0) op=0;
			else op=1;
			vd.push_back(op);
			bool ok=false;
			for(int i=0;i<6;i++) 
			{
				bool tok=true;
				for(int j=0;j<5;j++) if(vd[j]!=nz[(i-j+6)%6]) tok=false;
				if(tok) ok=true;
			}
			sig=true;
			if(ok) {pr=op; return pr;}
			else return -1;
		}
		
	}
}

Compilation message

Anthony.cpp: In function 'void {anonymous}::dfs(int, int, int)':
Anthony.cpp:11:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(g[s].size() + (s==0) ==2) {for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) {X[ind[s][i]]=nz[a]; dfs(g[s][i],s,(a+1)%6);}}
                                             ~^~~~~~~~~~~~
Anthony.cpp:12:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) {X[ind[s][i]]=nz[a]; dfs(g[s][i],s,1-nz[a]);}
                    ~^~~~~~~~~~~~
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int i=0;i<g[u].size();i++) if(d[g[u][i]]==-1)
                  ~^~~~~~~~~~~~
Anthony.cpp: At global scope:
Anthony.cpp:6:8: warning: '{anonymous}::b' defined but not used [-Wunused-variable]
  int a,b;
        ^

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

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 17368 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 962 ms 16688 KB Output is correct
4 Correct 1071 ms 18496 KB Output is correct
5 Correct 1025 ms 18436 KB Output is correct
6 Correct 1043 ms 17044 KB Output is correct
7 Correct 1055 ms 17140 KB Output is correct
8 Correct 1053 ms 17528 KB Output is correct
9 Correct 1057 ms 17860 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 17368 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 962 ms 16688 KB Output is correct
4 Correct 1071 ms 18496 KB Output is correct
5 Correct 1025 ms 18436 KB Output is correct
6 Correct 1043 ms 17044 KB Output is correct
7 Correct 1055 ms 17140 KB Output is correct
8 Correct 1053 ms 17528 KB Output is correct
9 Correct 1057 ms 17860 KB Output is correct
10 Correct 876 ms 15224 KB Output is correct
11 Correct 886 ms 15144 KB Output is correct
12 Correct 908 ms 15388 KB Output is correct
13 Correct 926 ms 15048 KB Output is correct
14 Correct 892 ms 15484 KB Output is correct
15 Correct 900 ms 15752 KB Output is correct
16 Correct 1053 ms 17984 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 14876 KB Output is correct
2 Correct 10 ms 2560 KB Output is correct
3 Correct 958 ms 14492 KB Output is correct
4 Correct 1040 ms 16276 KB Output is correct
5 Correct 1047 ms 16012 KB Output is correct
6 Correct 1031 ms 14852 KB Output is correct
7 Correct 1037 ms 14900 KB Output is correct
8 Correct 1039 ms 15608 KB Output is correct
9 Correct 1048 ms 15744 KB Output is correct
10 Correct 1020 ms 15320 KB Output is correct
11 Correct 1020 ms 15236 KB Output is correct
12 Correct 1047 ms 15360 KB Output is correct
13 Correct 1049 ms 15364 KB Output is correct
14 Correct 1055 ms 15696 KB Output is correct
15 Correct 1035 ms 15644 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 14876 KB Output is correct
2 Correct 10 ms 2560 KB Output is correct
3 Correct 958 ms 14492 KB Output is correct
4 Correct 1040 ms 16276 KB Output is correct
5 Correct 1047 ms 16012 KB Output is correct
6 Correct 1031 ms 14852 KB Output is correct
7 Correct 1037 ms 14900 KB Output is correct
8 Correct 1039 ms 15608 KB Output is correct
9 Correct 1048 ms 15744 KB Output is correct
10 Correct 1020 ms 15320 KB Output is correct
11 Correct 1020 ms 15236 KB Output is correct
12 Correct 1047 ms 15360 KB Output is correct
13 Correct 1049 ms 15364 KB Output is correct
14 Correct 1055 ms 15696 KB Output is correct
15 Correct 1035 ms 15644 KB Output is correct
16 Correct 885 ms 13324 KB Output is correct
17 Correct 870 ms 13360 KB Output is correct
18 Correct 900 ms 12980 KB Output is correct
19 Correct 865 ms 13176 KB Output is correct
20 Correct 884 ms 13684 KB Output is correct
21 Correct 884 ms 13692 KB Output is correct
22 Correct 1053 ms 15756 KB Output is correct
23 Correct 870 ms 13336 KB Output is correct
24 Correct 869 ms 13380 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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