Submission #212289

#	Time	Username	Problem	Language	Result	Execution time	Memory
212289		ksun48	Stray Cat (JOI20_stray)	C++14	100 / 100	121 ms	16828 KiB

Anthony

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

namespace {
	using namespace std;
	vector<vector<pair<int,int> > > edges;
	vector<int> marks;
	vector<int> arr = {0, 1, 0, 0, 1, 1};

	void dfs(int v, int pid, int idx){
		if(pid >= 0) marks[pid] = arr[idx];
		for(pair<int,int> e : edges[v]){
			if(e.second == pid) continue;
			if(edges[v].size() == 2){
				dfs(e.first, e.second, (idx + 1) % 6);
			} else {
				dfs(e.first, e.second, 1 ^ arr[idx]);
			}
		}
	}
	void mark_tree(int n, int m, vector<int> u, vector<int> v){
		edges.assign(n, {});
		for(int i = 0; i < m; i++){
			edges[u[i]].push_back({v[i], i});
			edges[v[i]].push_back({u[i], i});
		}
		marks.resize(m);
		dfs(0, -1, 0);
	}

	void mark_bfs(int n, int m, vector<int> u, vector<int> v){
		vector<vector<int> > e(n);
		for(int i = 0; i < m; i++){
			e[u[i]].push_back(v[i]);
			e[v[i]].push_back(u[i]);
		}
		vector<int> dist(n, -1);
		vector<int> bfs;
		int s = 0;
		bfs.push_back(0);
		dist[0] = 0;
		while(s < (int)bfs.size()){
			int x = bfs[s];
			s++;
			for(int w : e[x]){
				if(dist[w] >= 0) continue;
				dist[w] = dist[x] + 1;
				bfs.push_back(w);
			}
		}
		marks.resize(m);
		for(int i = 0; i < m; i++){
			marks[i] = min(dist[u[i]], dist[v[i]]) % 3;
		}
	}
	vector<int> mark(int n, int m, int a, int b, vector<int> u, vector<int> v){
		if(b > 0){
			mark_tree(n, m, u, v);
		} else {
			mark_bfs(n, m, u, v);
		}
		return marks;
	}
}  // namespace

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

Catherine

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

namespace {
	using namespace std;
	int a;
	int b;
	int last;
	vector<int> seen;
	bool good_to_go;
	void init(int _a, int _b){
		a = _a;
		b = _b;
		last = -1;
		good_to_go = false;
	}
	int move_tree(vector<int> y){
		vector<int> newy = y;
		if(last >= 0) newy[last]++;
		int deg = 0;
		for(int x : newy) deg += x;
		if(deg != 2){
			good_to_go = true;
		}
		if(good_to_go){
			if(deg == 1){
				if(last == -1){
					int r = 0;
					while(y[r] != 1) r++;
					last = r;
					return r;
				}
				return -1;
			} else if(deg == 2){
				assert(last != -1);
				int r = 0;
				while(y[r] != 1) r++;
				last = r;
				return r;
			} else {
				int r = 0;
				while(newy[r] != 1) r++;
				if(y[r] != 1){
					return -1;
				} else {
					last = r;
					return r;
				}
			}
		} else {
			assert(seen.size() < 5);
			if(last == -1){
				int r = 0;
				while(y[r] == 0) r++;
				seen.push_back(r);
				y[r]--;
				r = 0;
				while(y[r] == 0) r++;
				last = r;
				seen.push_back(r);
				return r;
			} else {
				int r = 0;
				while(y[r] == 0) r++;
				seen.push_back(r);
				if(seen.size() < 5){
					last = r;
					return r;
				} else {
					good_to_go = true;
					vector<vector<int> > okay = {
						{1, 1, 0, 0, 1},
						{1, 0, 0, 1, 0},
						{0, 0, 1, 0, 1},
						{0, 1, 0, 1, 1},
						{1, 0, 1, 1, 0},
						{0, 1, 1, 0, 0},
					};
					for(vector<int> v : okay){
						if(v == seen){
							last = r;
							return r;
						}
					}
					return -1;
				}
			}
		}
	}
	int move_bfs(vector<int> y){
		if(last >= 0){
			y[last]++;
		}
		for(int r = 0; r < 3; r++){
			if(y[r] && y[(r+1)%3]){
				assert(last != r);
				last = r;
				return last;
			}
		}
		int r = 0;
		while(y[r] == 0) r++;
		assert(last != r);
		last = r;
		return r;
	}
	int move(vector<int> y){
		if(b == 0){
			return move_bfs(y);
		} else {
			return move_tree(y);
		}
	}

}  // namespace

void Init(int A, int B) {
	init(A, B);
}

int Move(std::vector<int> y) {
	return move(y);
}

• 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