oj.uz

Submission #217463

# Submission time Handle Problem Language Result Execution time Memory
217463 2020-03-29T19:26:15 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1091 ms 17988 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) 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:74: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 1056 ms 16848 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 992 ms 16160 KB Output is correct
4 Correct 1028 ms 17940 KB Output is correct
5 Correct 1071 ms 17988 KB Output is correct
6 Correct 1036 ms 16692 KB Output is correct
7 Correct 1020 ms 16512 KB Output is correct
8 Correct 1034 ms 17328 KB Output is correct
9 Correct 1039 ms 17452 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1056 ms 16848 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 992 ms 16160 KB Output is correct
4 Correct 1028 ms 17940 KB Output is correct
5 Correct 1071 ms 17988 KB Output is correct
6 Correct 1036 ms 16692 KB Output is correct
7 Correct 1020 ms 16512 KB Output is correct
8 Correct 1034 ms 17328 KB Output is correct
9 Correct 1039 ms 17452 KB Output is correct
10 Correct 879 ms 14572 KB Output is correct
11 Correct 913 ms 14672 KB Output is correct
12 Correct 884 ms 14636 KB Output is correct
13 Correct 865 ms 14644 KB Output is correct
14 Correct 888 ms 14832 KB Output is correct
15 Correct 888 ms 15088 KB Output is correct
16 Correct 1051 ms 17492 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 14776 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 962 ms 14268 KB Output is correct
4 Correct 1035 ms 15760 KB Output is correct
5 Correct 1051 ms 15660 KB Output is correct
6 Correct 1030 ms 14616 KB Output is correct
7 Correct 1051 ms 14384 KB Output is correct
8 Correct 1089 ms 15100 KB Output is correct
9 Correct 1047 ms 15180 KB Output is correct
10 Correct 1025 ms 14888 KB Output is correct
11 Correct 1065 ms 14924 KB Output is correct
12 Correct 1091 ms 14844 KB Output is correct
13 Correct 1033 ms 15148 KB Output is correct
14 Correct 1040 ms 15092 KB Output is correct
15 Correct 1052 ms 15136 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 14776 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 962 ms 14268 KB Output is correct
4 Correct 1035 ms 15760 KB Output is correct
5 Correct 1051 ms 15660 KB Output is correct
6 Correct 1030 ms 14616 KB Output is correct
7 Correct 1051 ms 14384 KB Output is correct
8 Correct 1089 ms 15100 KB Output is correct
9 Correct 1047 ms 15180 KB Output is correct
10 Correct 1025 ms 14888 KB Output is correct
11 Correct 1065 ms 14924 KB Output is correct
12 Correct 1091 ms 14844 KB Output is correct
13 Correct 1033 ms 15148 KB Output is correct
14 Correct 1040 ms 15092 KB Output is correct
15 Correct 1052 ms 15136 KB Output is correct
16 Correct 885 ms 12888 KB Output is correct
17 Correct 853 ms 12900 KB Output is correct
18 Correct 893 ms 12716 KB Output is correct
19 Correct 856 ms 12976 KB Output is correct
20 Correct 917 ms 13168 KB Output is correct
21 Correct 888 ms 12916 KB Output is correct
22 Correct 1070 ms 15280 KB Output is correct
23 Correct 889 ms 12712 KB Output is correct
24 Correct 918 ms 12876 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 51 ms 12540 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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