oj.uz

Submission #217468

# Submission time Handle Problem Language Result Execution time Memory
217468 2020-03-29T19:58:58 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1110 ms 17880 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)
	{
		int x=1-nz[a];
		if(g[s].size() + (s==0) ==2) x=(a+1)%6;
		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,x);}
	}
}

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 && br!=1) 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:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   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,x);}
               ~^~~~~~~~~~~~
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:35: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:77: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 1063 ms 16848 KB Output is correct
2 Correct 10 ms 2560 KB Output is correct
3 Correct 969 ms 16172 KB Output is correct
4 Correct 1055 ms 17880 KB Output is correct
5 Correct 1059 ms 17836 KB Output is correct
6 Correct 1067 ms 16684 KB Output is correct
7 Correct 1035 ms 16636 KB Output is correct
8 Correct 1055 ms 17340 KB Output is correct
9 Correct 1052 ms 17316 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 16848 KB Output is correct
2 Correct 10 ms 2560 KB Output is correct
3 Correct 969 ms 16172 KB Output is correct
4 Correct 1055 ms 17880 KB Output is correct
5 Correct 1059 ms 17836 KB Output is correct
6 Correct 1067 ms 16684 KB Output is correct
7 Correct 1035 ms 16636 KB Output is correct
8 Correct 1055 ms 17340 KB Output is correct
9 Correct 1052 ms 17316 KB Output is correct
10 Correct 875 ms 14808 KB Output is correct
11 Correct 898 ms 14656 KB Output is correct
12 Correct 868 ms 14620 KB Output is correct
13 Correct 915 ms 14448 KB Output is correct
14 Correct 885 ms 14876 KB Output is correct
15 Correct 930 ms 15012 KB Output is correct
16 Correct 1053 ms 17428 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 14428 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 995 ms 14196 KB Output is correct
4 Correct 1053 ms 15820 KB Output is correct
5 Correct 1098 ms 15640 KB Output is correct
6 Correct 1047 ms 14416 KB Output is correct
7 Correct 1035 ms 14592 KB Output is correct
8 Correct 1063 ms 15084 KB Output is correct
9 Correct 1043 ms 15136 KB Output is correct
10 Correct 1055 ms 14892 KB Output is correct
11 Correct 1110 ms 15100 KB Output is correct
12 Correct 1030 ms 15132 KB Output is correct
13 Correct 1034 ms 14864 KB Output is correct
14 Correct 1083 ms 15156 KB Output is correct
15 Correct 1061 ms 15172 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 14428 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 995 ms 14196 KB Output is correct
4 Correct 1053 ms 15820 KB Output is correct
5 Correct 1098 ms 15640 KB Output is correct
6 Correct 1047 ms 14416 KB Output is correct
7 Correct 1035 ms 14592 KB Output is correct
8 Correct 1063 ms 15084 KB Output is correct
9 Correct 1043 ms 15136 KB Output is correct
10 Correct 1055 ms 14892 KB Output is correct
11 Correct 1110 ms 15100 KB Output is correct
12 Correct 1030 ms 15132 KB Output is correct
13 Correct 1034 ms 14864 KB Output is correct
14 Correct 1083 ms 15156 KB Output is correct
15 Correct 1061 ms 15172 KB Output is correct
16 Correct 891 ms 12912 KB Output is correct
17 Correct 850 ms 13044 KB Output is correct
18 Correct 907 ms 12732 KB Output is correct
19 Correct 905 ms 12800 KB Output is correct
20 Correct 910 ms 13188 KB Output is correct
21 Correct 875 ms 13192 KB Output is correct
22 Correct 1038 ms 15300 KB Output is correct
23 Correct 883 ms 12812 KB Output is correct
24 Correct 890 ms 12948 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 [5]
3 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12732 KB Output is correct
2 Incorrect 52 ms 13548 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -