oj.uz

Submission #217467

# Submission time Handle Problem Language Result Execution time Memory
217467 2020-03-29T19:38:54 Z Pajaraja Stray Cat (JOI20_stray) C++17
15 / 100
 1101 ms 18264 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 && 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: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 1063 ms 16856 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1006 ms 16148 KB Output is correct
4 Correct 1101 ms 18224 KB Output is correct
5 Correct 1033 ms 18264 KB Output is correct
6 Correct 1016 ms 16520 KB Output is correct
7 Correct 1060 ms 16688 KB Output is correct
8 Correct 1063 ms 17344 KB Output is correct
9 Correct 1043 ms 17472 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 16856 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 1006 ms 16148 KB Output is correct
4 Correct 1101 ms 18224 KB Output is correct
5 Correct 1033 ms 18264 KB Output is correct
6 Correct 1016 ms 16520 KB Output is correct
7 Correct 1060 ms 16688 KB Output is correct
8 Correct 1063 ms 17344 KB Output is correct
9 Correct 1043 ms 17472 KB Output is correct
10 Correct 899 ms 14584 KB Output is correct
11 Correct 863 ms 14900 KB Output is correct
12 Correct 881 ms 14636 KB Output is correct
13 Correct 855 ms 14636 KB Output is correct
14 Correct 883 ms 14976 KB Output is correct
15 Correct 886 ms 15140 KB Output is correct
16 Correct 1036 ms 17552 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 14372 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 978 ms 14100 KB Output is correct
4 Correct 1058 ms 15740 KB Output is correct
5 Correct 1020 ms 15820 KB Output is correct
6 Correct 1033 ms 14608 KB Output is correct
7 Correct 1043 ms 14608 KB Output is correct
8 Correct 1073 ms 15180 KB Output is correct
9 Correct 1034 ms 15028 KB Output is correct
10 Correct 1041 ms 14884 KB Output is correct
11 Correct 1020 ms 14916 KB Output is correct
12 Correct 1053 ms 15096 KB Output is correct
13 Correct 1057 ms 14884 KB Output is correct
14 Correct 1079 ms 15092 KB Output is correct
15 Correct 1032 ms 14992 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 14372 KB Output is correct
2 Correct 9 ms 2560 KB Output is correct
3 Correct 978 ms 14100 KB Output is correct
4 Correct 1058 ms 15740 KB Output is correct
5 Correct 1020 ms 15820 KB Output is correct
6 Correct 1033 ms 14608 KB Output is correct
7 Correct 1043 ms 14608 KB Output is correct
8 Correct 1073 ms 15180 KB Output is correct
9 Correct 1034 ms 15028 KB Output is correct
10 Correct 1041 ms 14884 KB Output is correct
11 Correct 1020 ms 14916 KB Output is correct
12 Correct 1053 ms 15096 KB Output is correct
13 Correct 1057 ms 14884 KB Output is correct
14 Correct 1079 ms 15092 KB Output is correct
15 Correct 1032 ms 14992 KB Output is correct
16 Correct 880 ms 12820 KB Output is correct
17 Correct 876 ms 12908 KB Output is correct
18 Correct 872 ms 12716 KB Output is correct
19 Correct 879 ms 12688 KB Output is correct
20 Correct 895 ms 13288 KB Output is correct
21 Correct 875 ms 13184 KB Output is correct
22 Correct 1053 ms 15320 KB Output is correct
23 Correct 869 ms 12760 KB Output is correct
24 Correct 903 ms 12760 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 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 52 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 54 ms 12636 KB Output is correct
2 Incorrect 50 ms 13548 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -