Submission #260632

#	Time	Username	Problem	Language	Result	Execution time	Memory
260632		amoo_safar	Stray Cat (JOI20_stray)	C++17	85 / 100	78 ms	14688 KiB

Anthony

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

#define pb push_back

using namespace std;

typedef pair<int, int> pii;

namespace {

const int N = 2e4 + 10;

int col[N];
vector<pii> G[N];

int pat[] = {0, 1, 0, 0, 1, 1};

void DFS(int u, int p, int pt = 0){
	int cnt = 0;
	for(auto [adj, id] : G[u]){
		if(adj != p) cnt ++;
	}
	if(cnt == 0) return ;
	if(cnt == 1){
		pt = (pt + 1) % 6;
	} else {
		pt = (pat[pt] == 0 ? 1 : 0);
	}
	if(u == 0) pt = 0;


	for(auto [adj, id] : G[u]){
		if(adj != p){
			DFS(adj, u, pt);
			col[id] = pat[pt];
		}
	}
}

}

vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
	assert(m == n - 1);
	assert(B >= 6);
	//cerr << "Salam\n";
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	DFS(0, -1);

	//cerr << "Bye\n";
	vector<int> C(m, 0);
	for(int i = 0; i < m; i++) C[i] = col[i];
	return C;
}

#ifdef safar
int main(){
	int n;
	cin >> n;
	vector<int> U1, V1, R;

	int u, v;
	for(int i = 0; i < n - 1; i++){
		cin >> u >> v;
		U1.pb(u);
		V1.pb(v);
	}
	R = Mark(n, n - 1, 2, 6, U1, V1);
	for(auto x : R) cerr << x << '\n';
}
#endif
/*
10
1 2
2 3
3 4
4 5
5 6
6 7
5 8
7 9
9 10

*/

Catherine

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

#define pb push_back

using namespace std;

typedef pair<int, int> pii;

namespace {

vector<int> vis, pa;
bool UP = false;


int MoveUp(vector<int> y){
	int deg = (vis.size() > 0 ? 1 : 0);
	for(auto x : y) deg += x;
	//cerr << "% " << deg << '\n';
	if(deg == 1 and !vis.empty()){
		return -1;
	}
	if(deg <= 2){
		for(int i = 0; i < 2; i++)
			if(y[i])
				return i;
	}
	//cerr << "$$ " << y[0] << ' ' << y[1] << '\n';
	int mn = 1'000'000'000;
	for(auto x : y) mn = min(x, mn);
	if(mn == 0) return -1;
	if(vis.empty())
		return (y[0] == 1 ? 0 : 1);
	return 1 - vis.back();
}

int Hand(int x){
	//cerr << "# " << x << '\n';
	if(x == -1) vis.pb(vis.back());
	else vis.pb(x);
	pa.pb(vis.back());

	return x;
}

bool Rev(){
	int sm = 3;
	for(auto x : pa) sm -= x;
	pa.pb(sm);
	for(int i = 0; i < 6; i++) pa.pb(pa[i]);
	for(int i = 0; i + 4 < (int)pa.size(); i ++){
		if((pa[i] == 0) && (pa[i+1] == 0) && (pa[i + 2] == 1) && (pa[i + 3] == 1)){
			return true;
		}
	}
	return false;
}

}  // namespace


void Init(int A, int B){
	assert(A == 2);
	assert(B >= 6);
}


int Move(vector<int> y){
	//cerr << "O\n";
	int deg = (vis.size() > 0 ? 1 : 0);
	for(auto x : y) deg += x;
	if(deg >= 3) UP = true;
	if(deg == 1) UP = true;
	//cerr << "A\n";
	if(UP) return Hand(MoveUp(y));
	//cerr << "E\n";

	if(vis.empty()){
		int idx;
		for(int i = 0; i < 2; i++) if(y[i]) idx = i;
		y[idx] -= 1;
		int idx2;
		for(int i = 0; i < 2; i++) if(y[i]) idx2 = i;
		
		pa.pb(idx2);
		return Hand(idx);
	}

	if(pa.size() < 4){
		int idx;
		for(int i = 0; i < 2; i++) if(y[i]) idx = i;
		return Hand(idx);
	}
	int idx;
	for(int i = 0; i < 2; i++) if(y[i]) idx = i;
	pa.pb(idx);

	if(Rev()){
		UP = true;
		return Hand(-1);
	}
	UP = true;
	return Hand(MoveUp(y));
}

Compilation message (stderr)

Anthony.cpp: In function 'void {anonymous}::DFS(int, int, int)':
Anthony.cpp:21:19: warning: unused variable 'id' [-Wunused-variable]
  for(auto [adj, id] : G[u]){
                   ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9