Submission #279740

#	Time	Username	Problem	Language	Result	Execution time	Memory
279740		tjd229	Stray Cat (JOI20_stray)	C++14	100 / 100	77 ms	17244 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <queue>

namespace {

	std::vector<int> edge[20000];
	int d[20000], m[20000];
	bool inq[20000];

	const int pat[6] = { 1,0,1,1,0,0 };

	void dfs(int x, int from) {

		if (x > 0 && edge[x].size() > 2) {//junction
			if (pat[m[from]] == 1) m[x] = 1;
			else m[x] = 0;
		}
		int nxtm = (m[x] + 1) % 6;
		for (auto nxt : edge[x]) {
			if (nxt == from) continue;
			d[nxt] = 1 + d[x];
			m[nxt] = nxtm;
			dfs(nxt, x);
		}
	}
	void bfs(int src) {
		std::queue<int> q; q.push(src);
		inq[src] = 1;
		while (q.size()) {
			int x = q.front(); q.pop();
			for (auto nxt : edge[x]) {
				if (inq[nxt]) continue;
				d[nxt] = d[x] + 1;
				q.push(nxt); inq[nxt] = 1;
			}
		}
	}

}  // namespace

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) {
		int u = U[i], v = V[i];
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	std::vector<int> X;
	if (B) {//tree
		dfs(0, 0);

		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (d[u] > d[v]) u ^= v ^= u ^= v;
			X.push_back(pat[m[u]]);
		}
	}

	else {
		bfs(0);
		for (int i = 0; i < M; ++i) {
			int u = U[i], v = V[i];
			if (d[u] > d[v]) u ^= v ^= u ^= v;
			X.push_back(d[u] % 3);
		}
	}
	return X;
}

Catherine

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

namespace {
	int _B;
	int _A;
	std::vector<int> hist;
	const int pat[6 + 6] = { 1,0,1,1,0,0 ,1,0,1,1,0,0 };//dn dir
	int mv = 0;
	bool dir = 0;
}  // namespace

void Init(int A, int B) {
	_A = A, _B = B;
}
int soft_move(std::vector<int> &y) {
	if (dir) {
		if (y[0] + y[1] > 1) {
			int prev = hist.back();
			++y[prev];
			int nxt = y[0] == 1 ? 0 : 1;
			hist.push_back(nxt);
		}
		else {
			int nxt = y[0] ? 0 : 1;
			hist.push_back(nxt);
		}
		return hist.back();
	}
	else {
		if (mv == 0) {//init
			if (y[1]==1 &&y[0] == 0) {//leaf
				dir = 1;
				hist.push_back(1);
				return 1;
			}
			else if (y[0] == 1 && y[1] == 0) {//leaf
				dir = 1;
				hist.push_back(0);
				return 0;
			}
			else if (y[0] + y[1] > 2) {//junc
				dir = 1;
				int nxt = y[0] == 1 ? 0 : 1;
				hist.push_back(nxt);
				return nxt;
			}
			while (y[0]--) hist.push_back(0);//1-way
			while (y[1]--) hist.push_back(1);
			++mv;
			return hist.back();
		}
		else if (y[0] + y[1] == 0) {//leaf;
			dir = 1;
			hist.push_back(hist.back());
			return -1;
		}
		else if (y[0] + y[1] > 1) {//junc 
			int prev = hist.back();
			int nxt = 1 - prev;
			dir = 1;

			if (y[nxt] == 1) {
				hist.push_back(nxt);
				return nxt;
			}
			else {
				hist.push_back(prev);
				return -1;
			}
		}
		else {//way
			int nxt = y[0] ? 0 : 1;
			if (mv++ == 3) {
				hist.push_back(nxt);
				dir = 1;
				for (int s = 0; s < 6; ++s) {
					bool flag = 1;
					for (int i = 0; i < 5 && flag; ++i) {
						if (hist[i] != pat[s + i]) flag = 0;
					}
					if (flag) {
						hist.pop_back();
						hist.push_back(hist.back());
						return -1;
					}
				}
				hist.push_back(nxt);
				return hist.back();
			}
			else {
				hist.push_back(nxt);
				return hist.back();
			}
		}
	}
}
int hard_move(std::vector<int> &y) {
	if (y[0] == 0 && y[1]) return 1;
	else if (y[1] == 0 && y[2]) return 2;
	else return 0;
}
int Move(std::vector<int> y) {
	if (_B) return soft_move(y);
	else return hard_move(y);
}

• 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