Submission #924411

#	Time	Username	Problem	Language	Result	Execution time	Memory
924411		socpite	Stray Cat (JOI20_stray)	C++14	100 / 100	43 ms	17292 KiB

Anthony

#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;


namespace {
	const int maxn = 2e4+5;
	vector<pair<int, int>> g[maxn];
	array<int, 6> pattern = {1, 0, 1, 0, 0, 1};

	int pos[maxn];
	vector<int> ans;

	void dfs(int x, int p){
		// cout << x << endl;
		int cc = 0;
		for(auto v: g[x]){
			if(v.second == p)continue;
			cc++;
		}
		if(cc == 1){
			// only child
			for(auto v: g[x]){
				if(v.second == p)continue;
				ans[v.second] = pattern[pos[x]];
				pos[v.first] = (pos[x]+1)%6;
				dfs(v.first, v.second);
			}
		} 
		else {
			for(auto v: g[x]){
				if(v.second == p)continue;
				ans[v.second] = p == -1 ? 0 : ans[p]^1;
				pos[v.first] = ans[v.second] ? 1 : 2;
				dfs(v.first, v.second);
			}
		}
	}

	void bfs(){
		queue<int> q;
		memset(pos, -1, sizeof(pos));
		pos[0] = 0;
		q.push(0);
		while(!q.empty()){
			auto x = q.front();
			q.pop();
			for(auto v: g[x]){
				if(pos[v.first] == -1){
					pos[v.first] = pos[x] + 1;
					q.push(v.first);
				}
			}
		}
	}
}  // namespace




std::vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {

	ans.resize(M);
	for(int i = 0; i < M; i++){
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	if(A == 2){
		for(int i = 0; i < N; i++){
			pos[i] = 0;
		}
		dfs(0, -1);
	}
	else {
		bfs();
		for(int i = 0; i < M; i++){
			ans[i] = min(pos[U[i]], pos[V[i]])%3;
		}
	}
	// for(auto v: ans)cout << v << " ";
	// cout << endl;
	return ans;
}

Catherine

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

//1001

namespace {
  	int A, B;
  	int variable_example = 0;
	int start = 1;
	int on_line = 0;
	int prv = 0;
	int ptr = 0;
	set<array<int, 5>> check = {
		{1, 0, 1, 0, 0},
		{0, 1, 0, 0, 1},
		{1, 0, 0, 1, 1},
		{0, 0, 1, 1, 0},
		{0, 1, 1, 0, 1},
		{1, 1, 0, 1, 0}
	};
	array<int, 5> crr;
}  // namespace

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

// MAX: <; MIN: >

int Move(std::vector<int> y) {
  	if(A == 2){
		if(start){
			start = 0;
			if(y[0] + y[1] != 2){
				if(min(y[0], y[1]) == 0)prv = y[0] < y[1];
				else prv = y[0] > y[1];
				return prv;
			}
			else {
				on_line = 1;
				prv = y[0] < y[1];
				// cout << prv << endl;
				y[prv]--;
				crr[ptr++] = y[0] < y[1];
				crr[ptr++] = prv;
				return prv;
			}
		}
		else{
			if(!on_line){
				if(min(y[0], y[1]) == 0)prv = y[0] < y[1];
				else prv^=1;
				return prv;
			}
			else {
				if(y[0] + y[1] != 1){
					on_line = 0;
					ptr = 0;
					if(min(y[0], y[1]) == 0)return -1;
					else {
						prv^=1;
						return prv;
					}
				}
				else{
					prv = y[0] < y[1];
					crr[ptr++] = prv;
					if(ptr == 5){
						on_line = 0;
						if(check.find(crr) == check.end())return prv;
						else {
							prv = crr[3];
							return -1;
						}
					}
					else return prv;
				}
			}
		}
  	}
	else{
		vector<int> vec;
		for(int i = 0; i < 3; i++)if(y[i])vec.push_back(i);
		if(vec.size() == 1)return vec[0];
		else {
			if(vec[0] == 0){
				if(vec[1] == 1)return 0;
				else return 2;
			}
			else return 1;
		}
	}
}

Compilation message (stderr)

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

• 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