Submission #260644

#	Time	Username	Problem	Language	Result	Execution time	Memory
260644		amoo_safar	Stray Cat (JOI20_stray)	C++17	100 / 100	70 ms	17860 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> Mark2(int n, int m, int A, int B, vector<int> U, vector<int> V) {
	
	//cerr << "Salam\n";
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	queue<int> Q;
	vector<int> dep(n, 1'000'000'000);
	dep[0] = 0;
	Q.push(0);
	int fr;
	while(!Q.empty()){
		fr = Q.front();
		Q.pop();

		for(auto [adj, id] : G[fr]){
			if(dep[adj] > dep[fr] + 1){
				dep[adj] = dep[fr] + 1;
				Q.push(adj);
			}
		}
	}


	//cerr << "Bye\n";
	vector<int> C(m, 0);
	for(int i = 0; i < m; i++) C[i] = min(dep[U[i]], dep[V[i]]) % 3;
	return C;
}


vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V) {
	if(B == 0){
		return Mark2(n, m, A, B, U, 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
/*
20 30 3 0 4
1 9
0 11
7 9
2 8
6 13
3 4
6 16
8 14
6 17
10 12
9 13
3 10
13 17
7 12
11 15
9 17
18 19
3 18
10 19
4 18
4 19
2 4
10 18
1 12
3 12
2 3
4 14
2 14
13 15
5 14

*/

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;
}

int state = 0;

int Move2(vector<int> y){
	if(!vis.empty()) y[vis.back()] ++;
	if(y[0] + y[1] == 0) return 2;
	if(y[0] + y[2] == 0) return 1;
	if(y[1] + y[2] == 0) return 0;
	if(y[2] == 0) return 0;
	if(y[0] == 0) return 1;
	if(y[1] == 0) return 2;
	return -1;
}

}  // namespace


void Init(int A, int B){
	if(B == 0) state = 1;
}


int Move(vector<int> y){
	if(state == 1) return Hand(Move2(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]){
                   ^
Anthony.cpp: In function 'std::vector<int> Mark2(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:59:20: warning: unused variable 'id' [-Wunused-variable]
   for(auto [adj, id] : G[fr]){
                    ^

• 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