oj.uz

Submission #217466

# Submission time Handle Problem Language Result Execution time Memory
217466 2020-03-29T19:36:32 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1082 ms 18004 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)
		{
			if(br!=1) y[pr]++;
			sig=true;
			int t;
			if(y[0]==1) t=0;
			if(y[1]==1) t=1;
			if(t==pr) return -1;
			else {pr=t; return pr;}
		}
		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:78: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 1024 ms 16820 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 968 ms 16132 KB Output is correct
4 Correct 1077 ms 17988 KB Output is correct
5 Correct 1034 ms 18004 KB Output is correct
6 Correct 1065 ms 16876 KB Output is correct
7 Correct 1006 ms 16520 KB Output is correct
8 Correct 1030 ms 17300 KB Output is correct
9 Correct 1032 ms 17364 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 16820 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 968 ms 16132 KB Output is correct
4 Correct 1077 ms 17988 KB Output is correct
5 Correct 1034 ms 18004 KB Output is correct
6 Correct 1065 ms 16876 KB Output is correct
7 Correct 1006 ms 16520 KB Output is correct
8 Correct 1030 ms 17300 KB Output is correct
9 Correct 1032 ms 17364 KB Output is correct
10 Correct 894 ms 14656 KB Output is correct
11 Correct 901 ms 14520 KB Output is correct
12 Correct 904 ms 14584 KB Output is correct
13 Correct 874 ms 14608 KB Output is correct
14 Correct 869 ms 14700 KB Output is correct
15 Correct 895 ms 15024 KB Output is correct
16 Correct 1034 ms 17468 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 14612 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 985 ms 14108 KB Output is correct
4 Correct 1056 ms 15768 KB Output is correct
5 Correct 1082 ms 15708 KB Output is correct
6 Correct 1010 ms 14552 KB Output is correct
7 Correct 1061 ms 14360 KB Output is correct
8 Correct 1035 ms 15156 KB Output is correct
9 Correct 1048 ms 15180 KB Output is correct
10 Correct 1053 ms 14924 KB Output is correct
11 Correct 1061 ms 14924 KB Output is correct
12 Correct 1055 ms 14920 KB Output is correct
13 Correct 1045 ms 14880 KB Output is correct
14 Correct 1054 ms 15184 KB Output is correct
15 Correct 1061 ms 15180 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 14612 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 985 ms 14108 KB Output is correct
4 Correct 1056 ms 15768 KB Output is correct
5 Correct 1082 ms 15708 KB Output is correct
6 Correct 1010 ms 14552 KB Output is correct
7 Correct 1061 ms 14360 KB Output is correct
8 Correct 1035 ms 15156 KB Output is correct
9 Correct 1048 ms 15180 KB Output is correct
10 Correct 1053 ms 14924 KB Output is correct
11 Correct 1061 ms 14924 KB Output is correct
12 Correct 1055 ms 14920 KB Output is correct
13 Correct 1045 ms 14880 KB Output is correct
14 Correct 1054 ms 15184 KB Output is correct
15 Correct 1061 ms 15180 KB Output is correct
16 Correct 876 ms 12844 KB Output is correct
17 Correct 885 ms 12776 KB Output is correct
18 Correct 904 ms 12708 KB Output is correct
19 Correct 893 ms 12744 KB Output is correct
20 Correct 909 ms 13440 KB Output is correct
21 Correct 883 ms 13188 KB Output is correct
22 Correct 1037 ms 15228 KB Output is correct
23 Correct 870 ms 12972 KB Output is correct
24 Correct 894 ms 12712 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2560 KB Output is correct
2 Incorrect 9 ms 2560 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 12608 KB Output is correct
2 Incorrect 51 ms 13776 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -