Submission #925981

#	Time	Username	Problem	Language	Result	Execution time	Memory
925981		mickey080929	Stray Cat (JOI20_stray)	C++17	100 / 100	42 ms	16772 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

int seq[6] = {0, 1, 1, 0, 0, 1};

vector<int> ret;
vector<pair<int,int>> adj[20010];

void dfs(int x, int p, int idx, int pc) {
	if (adj[x].size() == 1) return;
	if (adj[x].size() == 2) {
		if (adj[x][0].first == p) swap(adj[x][0], adj[x][1]);
		if (idx == -1) idx = pc;
		ret[adj[x][0].second] = seq[(idx+1) % 6];
		dfs(adj[x][0].first, x, (idx+1) % 6, seq[(idx+1) % 6]);
		return;
	}
	for (auto &[y, i] : adj[x]) {
		if (y == p) continue;
		ret[i] = pc ^ 1;
		dfs(y, x, -1, pc ^ 1);
	}
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
	ret.resize(M);
	for (int i=0; i<M; i++) {
		adj[U[i]].push_back({V[i], i});
		adj[V[i]].push_back({U[i], i});
	}
	if (A >= 3) {
		vector<int> dist(N, -1);
		queue<int> q;
		q.push(0);
		dist[0] = 0;
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (auto &[y, _] : adj[x]) {
				if (dist[y] == -1) {
					dist[y] = dist[x] + 1;
					q.push(y);
				}
			}
		}
		for (int i=0; i<M; i++) {
			ret[i] = min(dist[U[i]], dist[V[i]]) % 3;
		}
		return ret;
	}
	for (auto &[y, i] : adj[0]) {
		ret[i] = 0;
		dfs(y, 0, -1, 0);
	}
	return ret;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

int A, B;

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

int cnt = 0;
int prv = -1;
int seq[6] = {0, 1, 1, 0, 0, 1};
int read[6];

bool findDir() {
	for (int i=0; i<6; i++) {
		bool f = true;
		for (int j=0; j<6; j++) {
			if (read[(i+j) % 6] != seq[j]) {
				f = false;
				break;
			}
		}
		if (f) return true;
	}
	return false;
}

int Move(vector<int> y) {
	if (A >= 3) {
		if (y[0] && y[1]) return 0;
		if (y[1] && y[2]) return 1;
		if (y[2] && y[0]) return 2;
		if (y[0]) return 0;
		if (y[1]) return 1;
		if (y[2]) return 2;
		assert(0);
	}
	cnt ++;
	if (prv != -1) {
		if (y[0] + y[1] == 1) {
			if (y[0]) prv = 0;
			else prv = 1;
			return prv;
		}
		prv ^= 1;
		return prv;
	}
	if (cnt == 1) {
		if (y[0] == 1 && y[1] != 1) {
			return prv = 0;
		}
		if (y[0] != 1 && y[1] == 1) {
			return prv = 1;
		}
		assert(y[0] + y[1] == 2);
		if (y[0] == 2) {
			read[0] = read[1] = 0;
			return 0;
		}
		if (y[0] == 1) {
			read[0] = 0; read[1] = 1;
			return 1;
		}
		read[0] = read[1] = 1;
		return 1;
	}
	if (y[0] + y[1] != 1) {
		prv = read[cnt-1];
		if (!y[0] || !y[1]) return -1;
		assert(y[read[cnt-1] ^ 1]);
		return prv = (read[cnt-1] ^ 1);
	}
	read[cnt] = y[1];
	if (cnt == 4) {
		read[5] = 3 - read[0] - read[1] - read[2] - read[3] - read[4];
		prv = read[3];
		if (findDir()) return -1;
		return prv = read[4];
	}
	return read[cnt];
}

• 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