Submission #923704

#	Time	Username	Problem	Language	Result	Execution time	Memory
923704		daoquanglinh2007	Stray Cat (JOI20_stray)	C++17	15 / 100	40 ms	19564 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) (int)(a).size()
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e4, f[] = {0, 1, 0, 0, 1, 1};

vector <pii> adj[NM+5];
vector <int> ans;
queue <int> q;
int dep[NM+5];

void bfs(){
	for (int i = 0; i < NM; i++) dep[i] = -1;
	dep[0] = 0;
	while (!q.empty()) q.pop();
	q.push(0);
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (pii _ : adj[u]){
			int v = _.fi, id = _.se;
			if (dep[v] != -1){
				ans[id] = dep[v]%3;
			}
			else{
				ans[id] = dep[u]%3;
				dep[v] = dep[u]+1;
				q.push(v);
			}
		}
	}
}

void dfs(int u, int p, int m){
	int child = isz(adj[u])-(p != -1);
	if (child == 1 || p == -1){
		for (pii _ : adj[u]){
			int v = _.fi, id = _.se;
			if (v == p) continue;
			ans[id] = f[m];
			dfs(v, u, (m+1)%6);
		}
	}
	else{
		for (pii _ : adj[u]){
			int v = _.fi, id = _.se;
			if (v == p) continue;
			if (f[(m+5)%6] == 0){
				ans[id] = 1;
				dfs(v, u, 1);
			}
			else{
				ans[id] = 0;
				dfs(v, u, 0);
			}
		}
	}
}

vector <int> Mark(int N, int M, int A, int B, vector <int> U, vector <int> V){
	ans.resize(M);
	for (int i = 0; i < M; i++){
		adj[U[i]].push_back(mp(V[i], i));
		adj[V[i]].push_back(mp(U[i], i));
	}
	if (A > 2){
		bfs();
	}
	else{
		dfs(0, -1, 0);
	}
	return ans;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

int A, B;
int nMove = 0;
bool oriented = 0;
int lst = -1;
string s = "";
int tmp = -1;

void Init(int _A, int _B){
	A = _A, B = _B;
}

int Move(vector<int> y){
	if (A > 2){
		if (y[1] == 0 && y[2] == 0) return 0;
		if (y[0] == 0 && y[2] == 0) return 1;
		if (y[0] == 0 && y[1] == 0) return 2;
		if (y[2] == 0) return 0;
		if (y[0] == 0) return 1;
		return 2;
	}
	++nMove;
	if (oriented){
		if (y[0] == 0 && y[1] == 0) assert(0);
		if (y[0] == 0) return lst = 1, 1;
		if (y[1] == 0) return lst = 0, 0;
		if (lst == 0) return lst = 1, 1;
		return lst = 0, 0;
	}
	if (nMove == 1){
		if (y[0] == 0 && y[1] == 1){
			oriented = 1;
			return lst = 1, 1;
		}
		if (y[1] == 0 && y[0] == 1){
			oriented = 1;
			return lst = 0, 0;
		}
		if (y[1] == 1 && y[0] > 1){
			oriented = 1;
			return lst = 1, 1;
		}
		if (y[0] == 1 && y[1] > 1){
			oriented = 1;
			return lst = 0, 0;
		}
		if (y[0] == 0 && y[1] == 2){
			s.push_back('1');
			tmp = 1;
			return lst = 1, 1;
		}
		if (y[0] == 2 && y[1] == 0){
			s.push_back('0');
			tmp = 0;
			return lst = 0, 0;
		}
		s.push_back('0');
		tmp = 1;
		return lst = 0, 0;
	}
	if (y[0] == 0 && y[1] == 0){
		oriented = 1;
		return -1;
	}
	if (y[0] == 0 && y[1] > 1){
		oriented = 1;
		return -1;
	}
	if (y[1] == 0 && y[0] > 1){
		oriented = 1;
		return -1;
	}
	if (y[0] > 0 && y[1] > 0){
		oriented = 1;
		if (lst == 0) return lst = 1, 1;
		return lst = 0, 0;
	}
	if (nMove < 4){
		if (y[0] > 0){
			s.push_back('0');
			return lst = 0, 0;
		}
		s.push_back('1');
		return lst = 1, 1;
	}
	oriented = 1;
	
	if (s == "001" && y[1] > 0) return -1;
	if (s == "010" && y[0] > 0) return -1;
	if (s == "101" && y[0] > 0) return -1;
	if (s == "110" && y[1] > 0) return -1;
	
	if (s == "100" && y[1] > 0 && tmp == 0) return -1;
	if (s == "011" && y[0] > 0 && tmp == 0) return -1;
	
	if (y[0] > 0) return lst = 0, 0;
	return lst = 1, 1;
}

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