Submission #445222

#	Time	Username	Problem	Language	Result	Execution time	Memory
445222		flappybird	Stray Cat (JOI20_stray)	C++14	96 / 100	63 ms	21012 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define MAX 101010

namespace {
	vector<ll> adj[MAX], num[MAX], depth, deg, arr;
	vector<ll> ret;
	ll asdf[6] = { 1, 1, 0, 1, 0, 0 };
	void dfs(ll x = 0, ll p = -1, ll d = 1, ll str = 0, ll chk = 0) {
		depth[x] = d;
		ll i;
		for (i = 0; i < (int)adj[x].size(); i++) {
			if (adj[x][i] == p) continue;
			if (deg[adj[x][i]] == 2) {
				if (!chk) {
					while (d != asdf[str % 6]) str++;
				}
				ret[num[x][i]] = asdf[str % 6];
				dfs(adj[x][i], x, !asdf[str % 6], str + 1, 1);
			}
			else {
				ret[num[x][i]] = d;
				dfs(adj[x][i], x, !d);
			}
		}
	}
	void bfs() {
		queue<pair<ll, ll>> q;
		q.push({ 0, 0 });
		while (!q.empty()) {
			pair<ll, ll> t;
			t = q.front();
			q.pop();
			ll v = t.first;
			if (arr[v] != -1) continue;
			arr[v] = t.second;
			for (auto x : adj[v]) {
				q.push({ x, (t.second + 1) % 3 });
			}
		}
	}
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V) {
	if (A == 3) {
		ll i;
		for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
		for (i = 0; i < M; i++) num[U[i]].push_back(i);
		for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
		for (i = 0; i < M; i++) num[V[i]].push_back(i);
		ret.resize(M);
		arr.resize(N);
		for (i = 0; i < M; i++) ret[i] = -1;
		for (i = 0; i < N; i++) arr[i] = -1;
		bfs();
		for (i = 0; i < M; i++) {
			if (arr[U[i]] == arr[V[i]]) ret[i] = arr[U[i]];
			else {
				ll u, v;
				u = min(arr[U[i]], arr[V[i]]);
				v = max(arr[U[i]], arr[V[i]]);
				if (u == 0 && v == 1) ret[i] = 0;
				if (u == 1 && v == 2) ret[i] = 1;
				if (u == 0 && v == 2) ret[i] = 2;
			}
		}
		return ret;
	}
	ret.resize(M);
	deg.resize(N);
	ll i;
	for (i = 0; i < M; i++) adj[U[i]].push_back(V[i]);
	for (i = 0; i < M; i++) num[U[i]].push_back(i);
	for (i = 0; i < M; i++) adj[V[i]].push_back(U[i]);
	for (i = 0; i < M; i++) num[V[i]].push_back(i);
	for (i = 0; i < M; i++) deg[U[i]]++, deg[V[i]]++;
	depth.resize(N);
	dfs();
	return ret;
}

Catherine

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

namespace {

int A, B;
int variable_example = 0;
ll pv;
ll str;
ll last;
string up[6], down[6];

bool chk(string s) {
	for (ll i = 0; i < 6; i++) {
		if (s == up[i]) return true;
	}
	return false;
}

string s;

}  // namespace

void Init(int A, int B) {
	::A = A;
	::B = B;
	pv = -1;
	str = 0;
	last = 0;
	up[0] = "00101";
	up[1] = "01011";
	up[2] = "10110";
	up[3] = "01100";
	up[4] = "11001";
	up[5] = "10010";
}

int Move(std::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;
	}
	if (pv != -1) {
		if ((y[0] + y[1] + 1) != 2) {
			str = 0;
			s.clear();
			last = 1;
			y[pv]++;
			if (y[0] == 1) {
				if (pv == 0) return -1;
				else return pv = 0;
			}
			else {
				if (pv == 1) return -1;
				else return pv = 1;
			}
		}
		else {
			if (!last) {
				str++;
				ll nxt;
				if (y[0]) nxt = 0;
				else nxt = 1;
				s.push_back(nxt + 48);
				if (str == 5) {
					if (chk(s)) {
						last = 1;
						str = 0;
						s.clear();
						return pv = nxt;
					}
					else {
						last = 1;
						str = 0;
						s.clear();
						return -1;
					}
				}
				else {
					return pv = nxt;
				}
			}
			else {
				if (!(y[0] + y[1])) return -1;
				if (y[0]) return pv = 0;
				else return pv = 1;
			}
		}
	}
	else {
		if ((y[0] + y[1]) != 2) {
			last = 1;
			if (!(y[0] + y[1])) return -1;
			if (y[0] == 1) return pv = 0;
			else return pv = 1;
		}
		else {
			if (y[0] == 2) {
				s.push_back('0');
				s.push_back('0');
				str += 2;
				return pv = 0;
			}
			else if (y[1] == 2) {
				s.push_back('1');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
			else {
				s.push_back('0');
				s.push_back('1');
				str += 2;
				return pv = 1;
			}
		}
	}
}

Compilation message (stderr)

Catherine.cpp:9:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    9 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

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