Submission #218194

#	Time	Username	Problem	Language	Result	Execution time	Memory
218194		_7_7_	Stray Cat (JOI20_stray)	C++14	100 / 100	83 ms	19716 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 2e4 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 
namespace {
vi g[N], res, G = {0, 1, 0, 0, 1, 1};
unordered_map < int, int > gg[N];
queue < int > q;
int n, d[N];
}


void dfs (int v, int par = 0, int c = 0) {
	int son = sz(g[v]) - 1 + (!v), cc;
	if (son == 1)
		cc = (c + 1) % 6;
	else
		cc = 1 - G[c];

	for (auto to : g[v])
		if (to != par) {
			res[gg[v][to]] = G[cc];
			dfs(to, v, cc);
		}
}

 
 
vi Mark(int _n, int m, int A, int B, vi U, vi V) {
	n = _n;
	res.resize(m);
 
	for (int i = 0; i < m; ++i) {
		g[V[i]].pb(U[i]); 
		g[U[i]].pb(V[i]);
		gg[V[i]][U[i]] = gg[U[i]][V[i]] = i;
	}
	
	memset(d, -1, sizeof(d));
	q.push(0);
	d[0] = 0;
	while (sz(q)) {
		int v = q.front();
		q.pop();
		for (auto to : g[v])
			if (d[to] == -1) {
				d[to] = d[v] + 1;
				q.push(to);
			}
	}

	if (A > 2) 
		for (int i = 0; i < m; ++i)
			res[i] = min(d[V[i]], d[U[i]]) % A;
	else 
		dfs(0);
	/*for (int i = 0; i < m; ++i)
		cerr << res[i] << ' ';*/	
 
	return res;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 3e5 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;
 
namespace {
vi vv, G = {0, 1, 0, 0, 1, 1};
int A, B, timer, lst = -1;
bool ok;
}
 
 
void Init(int _A, int _B) {
	A = _A;
	B = _B;                       	
}
 
int Move(vi y) {
    if (A > 2) { 
		int a = -1, b = -1;
		for (int i = 0; i < sz(y); ++i)
			if (y[i]) {
				if (a == -1)
					a = i;
				else if (b == -1)
					b = i;
				else 
					assert(0);			
			}
		if (b == -1)
			return a;
 	
		if (b == A - 1 && a == 0)
			return b;
		return a;
	}
 
	++timer;
	int deg = y[0] + y[1] + (lst > -1);
	if (ok) {
		if (deg >= 3) 
			return lst = 1 - lst; 
 
		if (y[0])
			return lst = 0;
		if (y[1])
			return lst = 1;
		return -1;
	}
 
	if (deg == 1) {
		ok = 1;
		if (lst != -1)
			return -1;
		if (y[0])
			return lst = 0;
//		assert(y[1]);
		return lst = 1;
	}
	            
	if (deg > 2) {
		ok = 1;
		if (lst > -1)
			++y[lst];
		
		int a = y[0] == 1 ? 0 : 1;
//		assert(y[a] == 1);
		if (lst == a)
			return -1;
		return lst = a;					
	}
 
	//deg == 2
	if (timer == 4) {
		int a = y[0] ? 0 : 1;
//		assert(y[a]);
		vv.pb(a);
		bool found = 0;
		for (int i = 0; i < 6; ++i) {
			bool tmp = 1;
			for (int j = 0; j < 5; ++j)		
				if (vv[4 - j] != G[(i + j) % 6]) {
					tmp = 0;
					break;
				}
 
			if (tmp)
				found = 1;
		}
 
		ok = 1;
		if (found) 
			return lst = a;
		return -1;						
	}
 
	//deg = 2 and timer <= 3
	int a = y[0] ? 0 : 1;
 
	if (timer == 1) {
		vv.pb(y[a] == 2 ? a : 1 - a);
	}
		
	vv.pb(a);		
//	assert(y[a]);
	return lst = a;
}
	

• 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