Submission #216736

#	Time	Username	Problem	Language	Result	Execution time	Memory
216736		ainta	Stray Cat (JOI20_stray)	C++17	100 / 100	72 ms	17568 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <algorithm>
#include <cstdio>
#define N_ 20100
using namespace std;

vector<int>E[N_];
int Q[N_], D[N_], w[6] = { 0,0,1,1,0,1 }, T[N_], Dep[N_], Col[N_], BB;

void DFS(int a, int pp) {
	int c = E[a].size();
	if (a)c--;
	if (c >= 2)T[a] = 0;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		T[x] = T[a] + 1;

		if (a == 0) {
			Col[x] = 1;
		}
		else {
			if (T[a] == 0)Col[x] = !Col[a];
			else Col[x] = w[(T[a] - 1) % 6];
		}

		Dep[x] = Dep[a] + 1;
		DFS(x, a);
	}
}


std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  std::vector<int> X(M);
  int i;
  BB = B;
  for (i = 0; i < M; i++) {
	  E[U[i]].push_back(V[i]);
	  E[V[i]].push_back(U[i]);
  }
  Dep[0] = 0;
  if (BB) {
	  DFS(0, 0);
	  for (i = 0; i < M; i++) {
		  if (Dep[U[i]] < Dep[V[i]])X[i] = Col[V[i]];
		  else X[i] = Col[U[i]];
	  }
  }
  else {
	  int head = 0, tail = 0;
	  Q[++tail] = 0;
	  for (i = 0; i <= N; i++)D[i] = 1e9;
	  D[0] = 0;
	  while (head < tail) {
		  int x = Q[++head];
		  for (auto &t : E[x]) {
			  if (D[t] > D[x] + 1) {
				  D[t] = D[x] + 1;
				  Q[++tail] = t;
			  }
		  }
	  }
	  for (i = 0; i < M; i++) {
		  X[i] = min(D[U[i]], D[V[i]]) % 3;
	  }
  }
  return X;
}

Catherine

#include "Catherine.h"
#include <vector>


int s, ok, dd, BBB;
int L[3];
void Init(int A, int B) {
	BBB = B;
	s = 0; L[0] = L[1] = L[2] = -1;
	ok = 0;
	dd = 0;
}
void Put(int a) {
	L[2] = L[1];
	L[1] = L[0];
	L[0] = a;
	s++;
}
int Move(std::vector<int> y) {
	int i;
	if (BBB == 0) {
		if (!y[0]) {
			if (!y[1])return 2;
			return 1;
		}
		if (!y[1]) {
			if (!y[2])return 0;
			return 2;
		}
		if (!y[2]) {
			if (!y[0])return 1;
			return 0;
		}
	}
	if (ok) {
		int x;
		if (!y[0]) x = 1;
		else if (!y[1]) x = 0;
		else  x = !L[0];
		Put(x);
		return x;
	}
	if (!s) {
		if (y[0] + y[1] >= 3) {
			ok = 1;
			if (y[0] == 1) {
				Put(0); return 0;
			}
			if (y[1] == 1) {
				Put(1); return 1;
			}
		}
		if (y[0] + y[1] == 1) {
			ok = 1;
			if (y[0]) {
				Put(0); return 0;
			}
			else {
				Put(1); return 1;
			}
		}
		if (y[1] == 2 || y[0] == 2)dd = 1;
		if (y[1]) {
			Put(1);
			return 1;
		}
		Put(0);
		return 0;
	}
	if (y[0] + y[1] >= 2) {
		ok = 1;
		if (!y[L[0]]) {
			Put(L[0]);
			return -1;
		}
		int x = !L[0];
		Put(x);
		return x;
	}
	if (y[0] + y[1] == 0) {
		ok = 1;
		Put(L[0]);
		return -1;
	}
	int cur = 0;
	if (y[0])cur = 0;
	else cur = 1;
	if (s < 2) {
		Put(cur);
		return cur;
	}
	if (s == 2) {
		if (dd) {
			ok = 1;
			if (L[1] == 0 && L[0] == 0) {
				Put(L[0]);
				return -1;
			}
			if (L[1] == 0) {
				if (cur == 0) {
					Put(cur); return cur;
				}
				else {
					Put(L[0]); return -1;
				}
			}
			else {
				if (cur == 0) {
					Put(cur); return cur;
				}
				else {
					Put(L[0]); return -1;
				}
			}
		}
		if (L[0] == 0) {
			ok = 1;
			if (cur == 1) {
				Put(cur); return cur;
			}
			else {
				Put(L[0]); return -1;
			}
		}
		Put(cur); return cur;
	}
	if (s == 3) {
		ok = 1;
		if (cur == 0) {
			Put(cur); return cur;
		}
		else {
			Put(L[0]); return -1;
		}
	}
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:20:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^
Catherine.cpp:136:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9