Submission #212438

#	Time	Username	Problem	Language	Result	Execution time	Memory
212438		spdskatr	Stray Cat (JOI20_stray)	C++14	91 / 100	153 ms	17932 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <cstdio>
#include <queue>
#include <cassert>
#include <algorithm>
#include <cstdlib>
using namespace std;

namespace {
	vector<int> graph[20005];
	int dists[20005], seen[20005];
	queue<int> bfs;
	// dfs
	vector<int> seq = { 0, 1, 1, 0, 0, 1 };
	vector<int> ch[20005];
	int depth[20005], col[20005];

	void dfs(int x, int p, int state) {
		for (int v : graph[x]) if (v != p) {
			ch[x].push_back(v);
			depth[v] = depth[x] + 1;
		}
		if (ch[x].size() == 0) return;
		if (ch[x].size() == 1) {
			col[ch[x][0]] = seq[(state + 1) % 6];
			dfs(ch[x][0], x, (state + 1) % 6);
		} else {
			for (int v : ch[x]) {
				col[v] = seq[state] ^ 1;
				dfs(v, x, col[v]);
			}
		}
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
	vector<int> res;
	for (int i = 0; i < M; i++) {
		graph[U[i]].push_back(V[i]);
		graph[V[i]].push_back(U[i]);
	}
	if (A >= 3) {
		seen[0] = 1;
		bfs.push(0);
		while (!bfs.empty()) {
			int u = bfs.front(); bfs.pop();
			for (int v : graph[u]) if (!seen[v]) {
				seen[v] = 1;
				dists[v] = dists[u] + 1;
				bfs.push(v);
			}
		}
		//for (int i = 0; i < N; i++) fprintf(stderr, "dists[%d]: %d\n", i, dists[i]);
		for (int i = 0; i < M; i++) {
			int u = U[i], v = V[i];
			if (dists[u] != dists[v]) {
				res.push_back(min(dists[u], dists[v]) % 3);
			} else {
				res.push_back(dists[u] % 3);
			}
		}
	} else {
		dfs(0, 0, 1);
		for (int i = 0; i < M; i++) {
			int u = U[i], v = V[i];
			if (depth[u] > depth[v]) swap(u, v);
			res.push_back(col[v]);
		}
	}
	for (int i = 0; i < M; i++) fprintf(stderr, "Edge %d - %d marked %d\n", U[i], V[i], res[i]);
	return res;
}

Catherine

#include "Catherine.h"
#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>

using namespace std;

namespace {

int A, B;
int yay = 0;
int last = 0;
int initial = 1;
vector<int> seq = { 0, 1, 1, 0, 0, 1 };
vector<int> steps;

}  // namespace

void Init(int A, int B) {
	steps.clear();
	initial = 1;
	yay = 0;
	last = 0;
  ::A = A;
  ::B = B;
}

int _move(std::vector<int> y) {
	if (A >= 3) {
		if (y[0] == 0) {
			if (y[1] == 0) return 2;
			return 1;
		} else if (y[1] == 0) {
			if (y[2] == 0) return 0;
			return 2;
		} else {
			return 0;
		}
	} else {
		if (y[0] == 0 && y[1] == 0) {
			steps.clear();
			yay = 1;
			initial = 0;
			return -1;
		} else if (initial && y[0] + y[1] == 2) {
			// Go in a random direction
			steps.push_back(y[1] > 0);
			initial = 0;
			return last = y[1] > 0;
		} else if (y[0] + y[1] == 1) {
			if (yay) return last = (y[1] == 1);
			steps.push_back(y[1] == 1);
			int sz = steps.size();
			if (sz >= 4) {
				int cooked = 0;
				if (steps[sz-4] == 1) {
					if (steps[sz-3] == 1) {
						if (steps[sz-2] == 0 && steps[sz-1] == 0) cooked = 1;
					} else {
						if (steps[sz-2] == 1 && steps[sz-1] == 1) cooked = 1;
					}
				} else {
					if (steps[sz-3] == 1) {
						if (steps[sz-2] == 0 && steps[sz-1] == 1) cooked = 1;
					} else {
						if (steps[sz-2] == 1 && steps[sz-1] == 0) cooked = 1;
					}
				}
				if (cooked) {
					yay = 1;
					initial = 0;
					return -1;
				}
			}
			return last = (y[1] == 1);
		} else {
			steps.clear();
			if (y[0] == 0 || y[1] == 0) {
				yay = 1;
				initial = 0;
				return -1;
			} else {
				vector<int> rt = { y[0], y[1] };
				if (!initial) rt[last]++;
				yay = 1;
				initial = 0;
				return last = (rt[1] == 1);
			}
		}
	}
}
int Move(std::vector<int> y) {
	int res = _move(y);
	return res;
}

• 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: 0 / 9