Submission #212399

#	Time	Username	Problem	Language	Result	Execution time	Memory
212399		gs14004	Stray Cat (JOI20_stray)	C++17	100 / 100	234 ms	16884 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;

namespace {
	const int MAXN = 20005;
	vector<pi> gph[MAXN];
	int col[MAXN], pae[MAXN];
	void dfs(int x, int p){
		for(auto &[i, v] : gph[x]){
			if(v == p) continue;
			if(p == -1) col[i] = 0;
			else col[i] = col[pae[x]] ^ 1;
			pae[v] = i;
			if(sz(gph[v]) == 2){
				vector<int> seq = {x, v};
				while(sz(gph[seq.back()]) == 2){
					int w = seq.back();
					int nxt = -1;
					for(auto &k : gph[w]){
						if(k.second != seq[sz(seq) - 2]){
							nxt = k.second;
							pae[nxt] = k.first;
						}
					}
					seq.push_back(nxt);
				}
				vector<int> rpt; 
				if(col[i] == 0) rpt = {0, 1, 1, 0, 1, 0};
				else rpt = {1, 1, 0, 1, 0, 0};
				for(int i=2; i<sz(seq); i++){
					col[pae[seq[i]]] = rpt[(i - 1) % 6];
				}
				dfs(seq[sz(seq) - 1], seq[sz(seq) - 2]);
			}
			else{
				dfs(v, x);
			}
		}
	}
	int dist[MAXN];
	void bfs(int n, int x, int A){
		memset(dist, 0x3f, sizeof(dist));
		queue<int> que; que.push(x); dist[x] = 0;
		while(sz(que)){
			int x = que.front(); que.pop();
			for(auto &[i, j] : gph[x]){
				if(dist[j] > dist[x] + 1){
					dist[j] = dist[x] + 1;
					que.push(j);
				}
			}
		}
		for(int i=0; i<n; i++){
			for(auto &[j, v] : gph[i]){
				if(dist[i] <= dist[v]){
					col[j] = (dist[i] % A);
				}
			}
		}
	}
}  // 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<sz(U); i++){
    	gph[U[i]].emplace_back(i, V[i]);
    	gph[V[i]].emplace_back(i, U[i]);
	}
	if(A == 2) dfs(0, -1);
	else bfs(N, 0, A);
	return vector<int>(col, col + M);
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using pi = pair<int, int>;


namespace {
	int A;
	bool determined = 0;
	vector<int> prev_seq;
}  // namespace

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

bool bad_sign(vector<int> v){
	if(sz(v) >= 4){
		reverse(all(v));
		v.resize(4);
		reverse(all(v));
		if(v == vector<int>({1, 1, 0, 1})) return 1;
		if(v == vector<int>({0, 1, 0, 0})) return 1;
		if(v == vector<int>({1, 0, 1, 0})) return 1;
		if(v == vector<int>({0, 0, 1, 1})) return 1;
		return 0;
	}
	return 0;
}

int Move(std::vector<int> y) {
	if(A >= 3){
		if(sz(prev_seq)) y[prev_seq.back()]++;
		int ans = -1;
		for(int i=0; i<sz(y); i++){
			if(y[i]){
				if(y[(i + A - 1) % sz(y)]) ans = (i + A - 1) % A;
				else ans = i;
				break;
			}
		}
		prev_seq.push_back(ans);
		return ans;
	}
	int deg = accumulate(all(y), 0) + (sz(prev_seq) > 0);
	if(deg == 1){
		determined = 1;
		if(sz(prev_seq)){
			prev_seq.push_back(prev_seq.back());
			return -1;
		}
		int pos = find(all(y), 1) - y.begin();
		prev_seq.push_back(pos);
		return pos;
	}
	if(deg != 2){
		determined = 1;
		if(sz(prev_seq)){
			if(y[prev_seq.back()] == 0){
				prev_seq.push_back(prev_seq.back());
				return -1;
			}
			y[prev_seq.back()]++;
		}
		for(int i=0; i<sz(y); i++){
			if(y[i] == 1){
				prev_seq.push_back(i);
				return i; 
			}
		}
		assert(0);
	}
	vector<int> cands;
	for(int i=0; i<sz(y); i++){
		for(int j=0; j<y[i]; j++) cands.push_back(i);
	}
	if(sz(cands) == 2){
		prev_seq = cands;
		swap(prev_seq[0], prev_seq[1]);
	}
	else{
		prev_seq.push_back(cands[0]);
	}
	if(!determined && bad_sign(prev_seq)){
		determined = 1;
		prev_seq.pop_back();
		prev_seq.push_back(prev_seq.back());
		return -1;
	}
	return cands[0];
}

Compilation message (stderr)

Anthony.cpp: In function 'void {anonymous}::bfs(int, int, int)':
Anthony.cpp:50:19: warning: unused variable 'i' [-Wunused-variable]
    for(auto &[i, j] : gph[x]){
                   ^

• 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