Submission #212260

#	Time	Username	Problem	Language	Result	Execution time	Memory
212260		zscoder	Stray Cat (JOI20_stray)	C++17	100 / 100	133 ms	21324 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vector<ii> vec;
vector<ii> back;

struct Graph
{
	struct edge
	{
		int v; ll weight;
	};
	vector<vector<edge> > adj;
	int n;
	
	Graph(int _n)
	{
		adj.resize(_n);
		n = _n;
	}
	
	void addedge(int u, int v, ll c)
	{
		edge tmp;
		tmp.v = v; tmp.weight = c;
		adj[u].pb(tmp);
		tmp.v = u;
		adj[v].pb(tmp);
	}
	
	void reset()
	{
		adj.clear();
	}
	
	vector<ll> dist;
	vi par;
	
	void bfs(int s)
	{
		ll INFI = ll(1e18);
		dist.assign(n, INFI);
		par.assign(n, -1);
		dist[s] = 0; par[s] = -1;
		queue<int> q; q.push(s);
		while(!q.empty())
		{
			int u = q.front(); q.pop();
			for(int i = 0; i < adj[u].size(); i++)
			{
				int v = adj[u][i].v;
				if(dist[v] >= INFI)
				{
					vec.pb({u,v});
					dist[v] = dist[u] + 1;
					par[v] = u;
					q.push(v);
				}
				else
				{
					back.pb({u,v});
				}
			}
		}
	}
};

vi chain = {1,0,0,1,1,0};
int col[22222];
vi adj[22222];
int par[22222];
void dfs(int u, int p, int chainno=-1)
{
	int child=0;
	for(int v:adj[u])
	{
		if(v==p) continue;
		par[v]=u;
		child++;
	}
	if(child>=2)
	{
		for(int v:adj[u])
		{
			if(v==p) continue;
			col[v]=col[u]^1;
			dfs(v,u,-1);
		}
	}
	else if(child==1)
	{
		for(int v:adj[u])
		{
			if(v==p) continue;
			if(chainno>=0)
			{
				col[v] = chain[(chainno+1)%6];
				dfs(v,u,(chainno+1)%6);
			}
			else
			{
				col[v]=col[u]^1;
				if(col[v]==1) dfs(v,u,0);
				else dfs(v,u,1);
			}
		}
	}
}

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) 
{
	std::vector<int> ans(M);
	int n=N; int m=M;
	Graph G(n);
	map<ii,int> ma;
	for(int i=0;i<m;i++)
	{
		G.addedge(U[i],V[i],1);
		ma[{U[i],V[i]}]=ma[{V[i],U[i]}]=i;
		adj[U[i]].pb(V[i]);
		adj[V[i]].pb(U[i]);
	}
	G.bfs(0);
	if(A>=3)
	{
		for(ii x:vec)
		{
			int ed = ma[x];
			int mind = min(G.dist[x.fi],G.dist[x.se]);
			ans[ed]=mind%3;
		}
		for(ii x:back)
		{
			int ed = ma[x];
			int mind = min(G.dist[x.fi],G.dist[x.se]);
			ans[ed]=mind%3;
		}
		return ans;
	}
	col[0]=0;
	dfs(0,-1);
	for(int i=1;i<n;i++)
	{
		ans[ma[{i,par[i]}]] = col[i];
	}
	return ans;
}

Catherine

#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

namespace {

int A, B;
int beg = 0;
int up=0;
vi path;
vi chain = {1,0,0,1,1,0};

}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
  ::beg = 0;
  ::up = 0;
  ::path.clear();
}

int Move(std::vector<int> y) 
{
	if(A>=3)
	{
		int S[3]={};
		int mx=0;
		for(int i=0;i<3;i++)
		{
			if(y[i]>0) 
			{
				mx=i; S[i]=1;
			}
		}
		if(S[0]+S[1]+S[2]==1) return mx;
		if(S[0]&&S[1]) return 0;
		if(S[1]&&S[2]) return 1;
		return 2;
	}
	else
	{
		//rmb to check leaf case
		//cerr<<y[0]<<' '<<y[1]<<'\n';
		if(up) //if we are certain we are going up
		{
			if(y[0]+y[1]==1)
			{
				if(y[0]==1){path.pb(0); return 0;}
				path.pb(1); return 1;
			}
			path.pb((path.back()^1));
			return path.back();
		}
		if(!beg)
		{
			if(y[0]+y[1]==1)
			{
				up=1;
				if(y[1]==1){path.pb(1); return 1;}
				else{path.pb(0); return 0;}
			}
			if(y[0]+y[1]>2)
			{
				up=1;
				if(y[0]==1){path.pb(0); return 0;}
				if(y[1]==1){path.pb(1); return 1;}
				assert(0);
			}
			if(y[0]>0) 
			{
				y[0]--; path.pb(0); 
			}
			else 
			{
				y[1]--; path.pb(1);
			}
			if(y[0]>0) path.pb(0);
			else path.pb(1);
			reverse(path.begin(),path.end());
			beg=1;
			return path.back();
		}
		//got previous liao
		if(y[0]+y[1]==0)
		{
			up=1;
			return -1; //can go back
		}
		if(y[0]==0&&y[1]>1)
		{
			up=1;
			path.pb(0);
			return -1;
		}
		if(y[0]>1&&y[1]==0)
		{
			up=1;
			path.pb(1);
			return -1;
		}
		if(y[0]+y[1]>1)
		{
			up=1;
			y[path.back()]++;
			if(y[0]==1)
			{
				path.pb(0);
				return 0;
			}
			if(y[1]==1)
			{
				path.pb(1);
				return 1;
			}
			assert(0);
		}
		//chain now
		//cerr<<y[0]<<' '<<y[1]<<' '<<path[0]<<' '<<path.back()<<' '<<path.size()<<' '<<up<<'\n';
		if(path.size()>=4)
		{
			vi V;
			for(int i=int(path.size())-4;i<int(path.size());i++)
			{
				V.pb(path[i]);
			}
			if(y[0]==1)
			{
				V.pb(0);
			}
			else 
			{
				V.pb(1);
			}
			bool pos=0;
			for(int i=0;i<6;i++)
			{
				vi v2;
				for(int j=i;j<i+5;j++)
				{
					v2.pb(chain[j%6]);
				}
				if(v2==V){pos=1; break;}
			}
			if(pos) 
			{
				up=1; return -1;
			}
			else up=1;
		}
		if(y[0]==1)
		{
			path.pb(0); return 0;
		}
		if(y[1]==1)
		{
			path.pb(1); return 1;
		}
		assert(0);
	}
}

Compilation message (stderr)

Anthony.cpp: In member function 'void Graph::bfs(int)':
Anthony.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < adj[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~

• 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