oj.uz

Submission #217465

# Submission time Handle Problem Language Result Execution time Memory
217465 2020-03-29T19:29:35 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1103 ms 18008 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) pr=0;
			else pr=1;
			return pr;
		}
		if(deg==1) 
		{
			sig=true;
			if(br!=1) return -1;
			if(y[0]!=0) pr=0;
			else pr=1;
			return pr; 
		}
		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:75: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 1066 ms 16840 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1020 ms 16148 KB Output is correct
4 Correct 1103 ms 18008 KB Output is correct
5 Correct 1061 ms 17980 KB Output is correct
6 Correct 1069 ms 16684 KB Output is correct
7 Correct 1016 ms 16868 KB Output is correct
8 Correct 1081 ms 17324 KB Output is correct
9 Correct 1085 ms 17364 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1066 ms 16840 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1020 ms 16148 KB Output is correct
4 Correct 1103 ms 18008 KB Output is correct
5 Correct 1061 ms 17980 KB Output is correct
6 Correct 1069 ms 16684 KB Output is correct
7 Correct 1016 ms 16868 KB Output is correct
8 Correct 1081 ms 17324 KB Output is correct
9 Correct 1085 ms 17364 KB Output is correct
10 Correct 938 ms 14804 KB Output is correct
11 Correct 890 ms 14660 KB Output is correct
12 Correct 875 ms 14932 KB Output is correct
13 Correct 872 ms 14700 KB Output is correct
14 Correct 912 ms 14832 KB Output is correct
15 Correct 871 ms 15360 KB Output is correct
16 Correct 1067 ms 17456 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 14392 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1033 ms 14004 KB Output is correct
4 Correct 1042 ms 15800 KB Output is correct
5 Correct 1085 ms 15780 KB Output is correct
6 Correct 1052 ms 14552 KB Output is correct
7 Correct 1041 ms 14508 KB Output is correct
8 Correct 1071 ms 15128 KB Output is correct
9 Correct 1085 ms 14992 KB Output is correct
10 Correct 1095 ms 14716 KB Output is correct
11 Correct 1095 ms 15148 KB Output is correct
12 Correct 1049 ms 14924 KB Output is correct
13 Correct 1035 ms 14884 KB Output is correct
14 Correct 1060 ms 15176 KB Output is correct
15 Correct 1051 ms 15580 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1085 ms 14392 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1033 ms 14004 KB Output is correct
4 Correct 1042 ms 15800 KB Output is correct
5 Correct 1085 ms 15780 KB Output is correct
6 Correct 1052 ms 14552 KB Output is correct
7 Correct 1041 ms 14508 KB Output is correct
8 Correct 1071 ms 15128 KB Output is correct
9 Correct 1085 ms 14992 KB Output is correct
10 Correct 1095 ms 14716 KB Output is correct
11 Correct 1095 ms 15148 KB Output is correct
12 Correct 1049 ms 14924 KB Output is correct
13 Correct 1035 ms 14884 KB Output is correct
14 Correct 1060 ms 15176 KB Output is correct
15 Correct 1051 ms 15580 KB Output is correct
16 Correct 870 ms 12920 KB Output is correct
17 Correct 843 ms 12908 KB Output is correct
18 Correct 905 ms 12688 KB Output is correct
19 Correct 937 ms 12716 KB Output is correct
20 Correct 905 ms 13444 KB Output is correct
21 Correct 907 ms 13252 KB Output is correct
22 Correct 1056 ms 15148 KB Output is correct
23 Correct 880 ms 12832 KB Output is correct
24 Correct 902 ms 12968 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 12584 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 12604 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -