Submission #221463

#	Time	Username	Problem	Language	Result	Execution time	Memory
221463		patrikpavic2	Stray Cat (JOI20_stray)	C++17	100 / 100	104 ms	17672 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>

#define PB push_back
#define X first
#define Y second

using namespace std;

namespace {
	const int N = 2e4 + 500;
	
	int kljuc[6] = {1, 1, 0, 0, 1, 0};
	int tko[N], dep[N], col[N], par[N], dis[N];
	vector < int > v2[N];
	vector < int > v[N];
	void dfs_glup(int x, int lst){
		dep[x] = dep[lst] + 1;
		par[x] = lst; 
		if(lst != x) 
			v[lst].PB(x);
		for(int y : v2[x])
			if(y != lst) 
				dfs_glup(y, x);
	}
	void dfs_pametan(int x){
		if(v[par[x]].size() > 1 || !par[x]){
			col[x] = !col[par[x]];
			for(int y : v[x])
				dfs_pametan(y);
			return;
		}
		if(!par[par[x]] || (v[par[par[x]]].size() > 1)){
			if(!col[par[x]]) 
				tko[par[x]] = 2;
		}
		tko[x] = (tko[par[x]] + 1) % 6;
		col[x] = kljuc[tko[x]];
		for(int y : v[x])
				dfs_pametan(y);
	}
	void bfs(){
		queue < int > q; q.push(0); dis[0] = 1;
		for(;!q.empty();q.pop()){
			int cur = q.front();
			for(int y : v[cur]){
				if(!dis[y]){
					dis[y] = dis[cur] + 1;
					q.push(y);
				}
			}
		}
	}
}  // namespace

vector<int> Mark(int n, int m, int a, int b, vector<int> u1, vector<int> u2) {
	vector < int > ans(m);
	if(a == 2){
		for(int i = 0;i < m;i++){
			v2[u1[i]].PB(u2[i]);
			v2[u2[i]].PB(u1[i]);
		} 
		dfs_glup(0, 0);// printf("glup gotov\n");
		for(int y : v[0]) dfs_pametan(y);
		//for(int i = 1;i < n;i++) printf("col[ %d ] = %d\n", i, col[i]);
		for(int i = 0;i < m;i++){
			if(dep[u1[i]] > dep[u2[i]])
				ans[i] = col[u1[i]];
			else
				ans[i] = col[u2[i]];
		}
		return ans;
	}
	else{
		for(int i = 0;i < m;i++){
			v[u1[i]].PB(u2[i]);
			v[u2[i]].PB(u1[i]);
		}
		bfs();
		for(int i = 0;i < m;i++){
			ans[i] = min(dis[u1[i]], dis[u2[i]]) % 3;
		}
		return ans;
	}
}

Catherine

#include "Catherine.h"
#include <vector>
#include <cstdio>

#define PB push_back

using namespace std;

namespace {
	int lst, start = 1;
	vector < int > pamt;
	int jednostavno = 0;
	int AA = 0;
}  // namespace

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

int Move(std::vector<int> y) {
	if(AA == 2){
		if(start){
			start = 0;
			if(y[0] + y[1] > 2){
				return lst = (y[0] > y[1]);
			}
			if(y[0] + y[1] == 1){
				jednostavno = 1;
				return lst = y[1];
			}
			if(y[1]){
				pamt.PB(1); 
				pamt.PB(y[1] - 1);
				return lst = y[1] - 1;
			}
			else{
				pamt.PB(0);
				pamt.PB(0);
				return lst = 0;
			}
		}
		if(jednostavno){
			if(y[0] + y[1] == 1)
				return lst = y[1];
			if(y[0] == y[1])
				return lst = !lst;
			return lst = (y[0] > y[1]);
		}
		if(y[0] + y[1] == 0){
			jednostavno = 1;
			return -1;
		}
		if(y[0] + y[1] > 1){
			jednostavno = 1;
			if(y[0] == 0 || y[1] == 0){
				return -1;
			}
			if(y[0] != y[1]){
				return lst = (y[0] > y[1]);
			}
			if(y[0] == y[1]){
				return lst = !lst;
			}
		}
		pamt.PB(y[1]);
		if((int)pamt.size() == 5){
			bool jed = (pamt ==  (vector<int>){1, 1, 0, 0, 1});
			jed |= (pamt ==  (vector<int>){1, 0, 0, 1, 0});
			jed |= (pamt ==  (vector<int>){0, 0, 1, 0, 1});
			jed |= (pamt ==  (vector<int>){0, 1, 0, 1, 1});
			jed |= (pamt ==  (vector<int>){1, 0, 1, 1, 0});
			jed |= (pamt ==  (vector<int>){0, 1, 1, 0, 0});
			jednostavno = 1;
			if(jed){
				return -1;
			}
			else{
				return lst = y[1];
			}
		}
		return lst = y[1];
	}
	else{
		if(!!y[0] + !!y[1] + !!y[2] == 1){
			if(y[0]) 
				return 0;
			if(y[1]) 
				return 1;
			return 2;
		}
		else{
			if(!y[0])
				return 1;
			if(!y[1])
				return 2;
			return 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