Submission #218029

#	Time	Username	Problem	Language	Result	Execution time	Memory
218029		mieszko11b	Stray Cat (JOI20_stray)	C++14	100 / 100	168 ms	19748 KiB

Anthony

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

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

namespace {
	vector<int> res;
	vector<ii> G[20007];
	vector<ii> ch[20007];
	int ord[] = {0, 0, 1, 0, 1, 1};
	bool vis[20007];
	int top[20007];
	bool intree[20007];

	void dfs(int w = 0, int p = -1, int o = -1, int c = 0) {
		int deg = G[w].size();
		if(p != -1) deg--;
		for(ii u : G[w]) {
			if(u.X != p) {
				if(deg > 1) {
					res[u.Y] = c ^ 1;
					dfs(u.X, w, -1, c ^ 1);
				} else {
					if(o == -1) {
						if(c == 0)
							o = 4;
						else
							o = 0;
					}
					res[u.Y] = ord[o];
					dfs(u.X, w, (o + 1) % 6, ord[o]);
				}
			}
		}
	}

	void dfs2(int w = 0, int p = -1, int c = 0) {
		for(ii u : ch[w]) {
			if(u.X != p) {
				res[u.Y] = c;
				intree[u.Y] = 1;
				top[u.X] = c;
				dfs2(u.X, w, (c + 1) % 3);
			}
		}
	}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
	res.resize(M);
	
	for(int i = 0 ; i < M ; i++) {
		int a = U[i];
		int b = V[i];
		G[a].emplace_back(b, i);
		G[b].emplace_back(a, i);
	}
	
	if(A == 2) {
		dfs();
	} else {
		queue<int> Q;
		vis[0] = 1;
		Q.push(0);
		while(!Q.empty()) {
			int w = Q.front();
			Q.pop();
			for(ii u : G[w]) {
				if(!vis[u.X]) {
					ch[w].emplace_back(u);
					vis[u.X] = 1;
					Q.push(u.X);
				}
			}
		}
		
		dfs2();
		
		for(int i = 0 ; i < M ; i++) {
			if(!intree[i]) {
				if(top[U[i]] == top[V[i]])
					res[i] = (top[U[i]] + 1) % 3;
				else {
					int a = top[U[i]];
					int b = top[V[i]];
					if(a > b) swap(a, b);
					if(a == 0 && b == 1) res[i] = 1;
					if(a == 0 && b == 2) res[i] = 0;
					if(a == 1 && b == 2) res[i] = 2;
				}
			}
		}
	}
	
	for(int i = 0 ; i < M ; i++)
		cerr << res[i] << " ";
	cerr << endl;
	
	return res;
}

Catherine

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

using namespace std;

namespace {

	int A, B;
	vector<int> hist;
	bool up;
	int ord[] = {0, 0, 1, 0, 1, 1};

}  // namespace

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

int Move(std::vector<int> y) {
	if(A > 2) {
		if((y[0] ? 1 : 0) + (y[1] ? 1 : 0) + (y[2] ? 1 : 0) == 1) {
			int k = 0;
			if(y[1]) k = 1;
			if(y[2]) k = 2;
			return k;
		}
		
		if(y[0] && y[1]) return 0;
		if(y[0] && y[2]) return 2;
		return 1;
	}
	
	if(up) {
		if(!y[0]) {
			hist.push_back(1);
			return 1;
		}
		if(!y[1]) {
			hist.push_back(0);
			return 0;
		}
		hist.push_back(hist.back() ^ 1);
		return hist.back();
	}
	
	if(hist.empty() && y[0] + y[1] == 1) {
		int k = 0;
		if(!y[0]) k = 1;
		hist.push_back(k);
		up = 1;
		return k;
	}
	
	int z[2];
	z[0] = y[0];
	z[1] = y[1];
	if(!hist.empty())
		z[hist.back()]++;
	
	if(z[0] > 1 && z[1] == 1) {
		hist.push_back(1);
		up  = true;
		return y[1] ? 1 : -1;
	}
	if(z[1] > 1 && z[0] == 1) {
		hist.push_back(0);
		up = true;
		return y[0] ? 0 : -1;
	}
	if(y[0] == 0 && y[1] == 0) {
		hist.push_back(hist.back());
		up = true;
		return -1;
	}
	
	if(hist.size() < 4) {
		vector<int> V;
		for(int x = 0 ; x < y[0] ; x++) V.push_back(0);
		for(int x = 0 ; x < y[1] ; x++) V.push_back(1);
		
		if(y[0] + y[1] == 2) {
			hist.push_back(V[0]);
			hist.push_back(V[1]);
			return V[1];
		}
		
		hist.push_back(V[0]);
		return V[0];
	}
	
	bool down = false;
	int k = 0;
	if(!y[0]) k = 1;
	for(int i = 0 ; i < 6 ; i++) {
		if(hist[0] == ord[i] && hist[1] == ord[(i+1) % 6] && hist[2] == ord[(i+2) % 6]
			&& hist[3] == ord[(i+3) % 6] && k == ord[(i+4) % 6]) {
				down = true;
			}
	}
	
	if(down) {
		hist.push_back(hist.back());
		up = 1;
		return -1;
	}
	
	up = 1;
	hist.push_back(k);
	return k;
}

• 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