Submission #262627

#	Time	Username	Problem	Language	Result	Execution time	Memory
262627		arnold518	Stray Cat (JOI20_stray)	C++14	100 / 100	71 ms	17416 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static const int MAXN = 2e4;

static int N, M, A, B, D[MAXN+10];
static pii E[MAXN+10];
static vector<pii> adj[MAXN+10];
static vector<int> ret;

static int S[10]={1, 1, 0, 1, 0, 0};

void dfs(int now, int bef, int col, int cnt)
{
	int chd=0;
	if(now==bef) chd=adj[now].size();
	else chd=adj[now].size()-1;
	if(chd>=2)
	{
		for(auto nxt : adj[now])
		{
			if(nxt.first==bef) continue;
			ret[nxt.second-1]=1-col;
			dfs(nxt.first, now, 1-col, 1-col);
		}
	}
	else if(chd==1)
	{
		for(auto nxt : adj[now])
		{
			if(nxt.first==bef) continue;
			ret[nxt.second-1]=S[cnt];
			dfs(nxt.first, now, S[cnt], (cnt+1)%6);
		}
	}
}

vector<int> Mark(int _N, int _M, int _A, int _B, vector<int> _U, vector<int> _V)
{
	N=_N; M=_M; A=_A; B=_B;
	for(int i=1; i<=M; i++)
	{
		int u=_U[i-1]+1, v=_V[i-1]+1;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
		E[i]={u, v};
	}
	ret.resize(M);

	if(B==0)
	{
		queue<int> Q;
		memset(D, -1, sizeof(D));
		Q.push(1); D[1]=0;
		while(!Q.empty())
		{
			int now=Q.front(); Q.pop();
			for(auto nxt : adj[now])
			{
				if(D[nxt.first]!=-1) continue;
				Q.push(nxt.first);
				D[nxt.first]=D[now]+1;
			}
		}
		for(int i=1; i<=M; i++) ret[i-1]=min(D[E[i].first], D[E[i].second])%3;
		return ret;
	}

	dfs(1, 1, 1, 0);
	return ret;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static const int MAXN = 2e4;
static int A, B;
static vector<int> V;
string S;
static int cnt, bef;
static bool up;

vector<string> VV = {"11010", "10100", "10011", "00110", "01101"};

void Init(int _A, int _B)
{
	A=_A; B=_B;
	cnt=0; up=false;
}

int Move(vector<int> _V)
{
	V=_V;
	cnt++;

	if(B==0)
	{
		if(V[0]==0 && V[1]==0) return 2;
		if(V[0]==0 && V[2]==0) return 1;
		if(V[2]==0 && V[1]==0) return 0;

		if(V[0]==0) return 1;
		if(V[1]==0) return 2;
		if(V[2]==0) return 0;
	}

	int deg=0;
	deg=V[0]+V[1];
	if(cnt!=1) deg++;

	if(cnt==1)
	{
		if(V[0]==1 && V[1]==0) { up=true; return bef=0; }
		if(V[0]==0 && V[1]==1) { up=true; return bef=1; }
		if(deg>=3)
		{
			up=true;
			if(V[0]==1) { return bef=0; }
			if(V[1]==1) { return bef=1; }
		}
		assert(deg==2);
		if(V[1]==2) { S.push_back('1'); S.push_back('1'); return bef=1; }
		if(V[0]==2) { S.push_back('0'); S.push_back('0'); return bef=0; }
		if(V[0]==1 && V[1]==1) { S.push_back('1'); S.push_back('0'); return bef=0; }
	}
	else
	{
		if(deg>=3)
		{
			up=true;
			if(V[0]==0) { return -1; }
			if(V[1]==0) { return -1; }
			bef=!bef;
			return bef;
		}
		if(deg==1)
		{
			up=true;
			return -1;
		}
		if(up)
		{
			if(V[1]==1) return bef=1;
			if(V[0]==1) return bef=0;
		}
		if(cnt<4)
		{
			if(V[1]==1) { S.push_back('1'); return bef=1; }
			if(V[0]==1) { S.push_back('0'); return bef=0; }
		}
		if(V[1]==1) S.push_back('1');
		else if(V[0]==1) S.push_back('0');

		bool flag=false;
		for(auto it : VV) if(it==S) flag=true;
		up=true;
		if(flag) return -1;
		else
		{
			if(V[1]==1) return bef=1;
			if(V[0]==1) return bef=0;
		}
	}

}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:98:1: warning: control reaches end of non-void function [-Wreturn-type]
   98 | }
      | ^

• 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