Submission #514030

#	Time	Username	Problem	Language	Result	Execution time	Memory
514030		8e7	Stray Cat (JOI20_stray)	C++17	100 / 100	52 ms	16824 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
#define maxn 20005
#define pii pair<int, int>
using namespace std;
namespace {
	vector<pii> adj[maxn];
	int res[maxn];
	int arr[6] = {0, 0, 1, 0, 1, 1};
	const int inf = 8e7;
	void dfs(int n, int par, int ind, int prv) {
		int deg = adj[n].size() - (par == -1 ? 0 : 1);
		if (deg == 1) {
			for (auto [v, id]:adj[n]) {
				if (v != par) {
					res[id] = arr[ind];
					dfs(v, n, (ind+1)%6, res[id]);
				}
			}
		} else {
			for (auto [v, id]:adj[n]) {
				if (v != par) {
					res[id] = prv ^ 1;
					dfs(v, n, res[id] ? 5 : 1, res[id]);
				}
			}
		}
	}	
}; 

vector<int> Mark(int N, int M, int A, int B,
                      vector<int> U, vector<int> V) {
	for (int i = 0;i < M;i++) adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
	vector<int> X(M);
	if (A >= 3) {
		queue<int> que;
		que.push(0);
		vector<int> d(N, inf);
		d[0] = 0;
		while (que.size()) {
			int cur = que.front();que.pop();
			for (auto[v, id] :adj[cur]) {
				if (d[cur] + 1 < d[v]) {
					d[v] = d[cur] + 1;
					que.push(v);
				}
			}
		}
		for (int i = 0; i < M; ++i) {
			if (d[U[i]] > d[V[i]]) swap(U[i], V[i]);
			X[i] = d[U[i]] % 3;
		}
	} else {
		dfs(0, -1, 0, 0);	
		for (int i = 0;i < M;i++) X[i] = res[i];
	}
	return X;
}

Catherine

#include "Catherine.h"
#include <vector>
#include "assert.h"
using namespace std;

namespace {
	int A, B;
	bool type = 0;
	int prv = 0, step = 0, mask = 0;
	int check[6] = {12, 25, 18, 5, 11, 22};
};  

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

int Move(vector<int> y) {	
	if (A >= 3) {
		int cnt = (y[0] ? 1 : 0) + (y[1] ? 1 : 0) + (y[2] ? 1 : 0);
		if (cnt == 1) {
			for (int i = 0;i < 3;i++) {
				if (y[i]) return i;
			}
		} else {
			if (y[0] && y[1]) return 0;
			else if (y[1] && y[2]) return 1;
			else if (y[2]) return 2;
		}
		return -1;
	} else {
		int sum = y[0] + y[1];
		sum += (step ? 1 : 0);	
		if (sum > 2) {
			step++;
			if (y[0] == 0 || y[1] == 0) {
				return -1;
			} 
			if (step > 1) y[prv]++;
			prv = y[0] == 1 ? 0 : 1;
			return prv;
		} else {
			if (step) sum--;
			step++;
			if (sum == 1) {
				if (type && step == 4) {
					mask = mask * 2 + (y[0] == 1 ? 0 : 1);
					bool match = 0;
					for (int i = 0;i < 6;i++) {
						if (mask == check[i]) match = 1;
					}	
					if (match) return -1;
				}
				prv = y[0] == 1 ? 0 : 1;
				if (step < 4) mask = mask * 2 + prv;
				return prv;
			} else {
				if (sum == 0) return -1;
				prv = y[0] ? 0 : 1;
				y[prv]--;
				type = 1;
				mask = (y[0] ? 0 : 1) * 2 + prv;
				return prv;	
			}
		}
	}
}
/*
11 10 2 6 6
0 2
0 3
0 4
3 5
5 7
5 8
7 10
4 6
6 9
9 1
*/

• 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