Submission #212223

#	Time	Username	Problem	Language	Result	Execution time	Memory
212223		pit4h	Stray Cat (JOI20_stray)	C++14	85 / 100	88 ms	16116 KiB

Anthony

#include "Anthony.h"
#include<bits/stdc++.h>
#define pii pair<int, int>
#define st first
#define nd second
using namespace std;
const int N = 2e4+1;
vector<int> mark;
vector<pii> g[N];
void dfs(int x, int p, bool cur, int len=0) {
	//~ cerr<<"dfs: "<<x<<' '<<p<<' '<<cur<<' '<<len<<' '<<g[x].size()<<'\n';
	for(auto i: g[x]) {
		if(i.st!=p) {
			if((int)g[i.st].size()!=2) {
				mark[i.nd]=cur;
				dfs(i.st, x, 1^cur);
			}
			else {
				mark[i.nd]=cur;
				if(g[x].size()!=2 && cur==1) {
					len=1;
				}
				bool nxt;
				if(len==0 || len==1 || len==4) nxt=1;
				else nxt=0;
				dfs(i.st, x, nxt, (len+1)%6);
			}
		}
	}
}
vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
  mark.resize(m);
  for(int i=0; i<m; ++i) {
	  g[u[i]].push_back({v[i], i});
	  g[v[i]].push_back({u[i], i});
  }
  dfs(0, 0, 0);
  return mark;
}

Catherine

#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;
int a, b;
void Init(int A, int B) {
	a = A;
	b = B;
}
int col=-1;
bool good_dir=0;
vector<int> path;
vector<vector<int>>v={{0, 1, 1, 0, 0},{1, 1, 0, 0, 1},{1, 0, 0, 1, 0},{0, 0, 1, 0, 1},{0, 1, 0, 1, 1},{1, 0, 1, 1, 0}};
int Move(vector<int> y) {
	int cnt=0;
	for(int i: y) cnt+=i;
	if(col==-1) {
		if(cnt==1) {
			good_dir=1;
			if(y[0]==1) {
				col=0;
				//~ cerr<<"go to: "<<col<<'\n';
				return 0;
			}
			col=1;
			//~ cerr<<"go to: "<<col<<'\n';
			return 1;
		} 
		if(cnt>2) {
			good_dir=1;
			assert(y[0]==1 || y[1]==1);
			if(y[0]==1) {
				col=0;
				//~ cerr<<"go to: "<<col<<'\n';
				return 0;
			}
			col=1;
			//~ cerr<<"go to: "<<col<<'\n';
			return 1;
		}
		if(cnt==2) {
			if(y[1]!=0) {
				if(y[0]==1) path.push_back(0);
				else path.push_back(1);
				path.push_back(1);
				col=1;
				//~ cerr<<"go to: "<<col<<'\n';
				return 1;
			}
			path.push_back(0);
			path.push_back(0);
			col=0;
			//~ cerr<<"go to: "<<col<<'\n';
			return 0;
		}
	}
	assert(col!=-1);
	if(cnt!=1) {
		path.clear();
		good_dir=1;
	}
	if(cnt==0) {
		//~ cerr<<"go to: "<<-1<<'\n';
		return -1;
	}
	if(cnt>=2) {
		if(y[col]==0) {
			//~ cerr<<"go to: "<<-1<<'\n';
			return -1;
		}
		col=1^col;
		//~ cerr<<"go to: "<<col<<'\n';
		return col;
	}
	//~ cerr<<"path size: "<<path.size()<<' '<<good_dir<<'\n';
	if(good_dir) {
		if(y[0]==1) {
			col=0;
			//~ cerr<<"go to: "<<col<<'\n';
			return 0;
		}
		assert(y[1]==1);
		col=1;
		//~ cerr<<"go to: "<<col<<'\n';
		return 1;
	}
	if((int)path.size()==4) {
		if(y[0]==1) {
			path.push_back(0);
		}
		else {
			path.push_back(1);
		}
		if(path==v[0] || path==v[1] || path==v[2] || path==v[3] || path==v[4] || path==v[5]) {	
			//~ cerr<<"wrong\n";
			good_dir=1;
			path.clear();
			//~ cerr<<"go to: "<<-1<<'\n';
			return -1;
		}
		else { 
			good_dir=1;
			path.clear();
			if(y[0]==1) {
				col=0;
				//~ cerr<<"go to: "<<col<<'\n';
				return 0;
			}
			col=1;
			//~ cerr<<"go to: "<<col<<'\n';
			return 1;
		}
	}
	assert(path.size()>0);
	assert(cnt==1);
	//~ if(path.empty()) {
		//~ path.push_back(col);
		//~ if(y[0]==1) {
			//~ path.push_back(0);
			//~ col=0;
			//~ cerr<<"go to: "<<col<<'\n';
			//~ return 0;
		//~ }
		//~ path.push_back(1);
		//~ col=1;
		//~ cerr<<"go to: "<<col<<'\n';
		//~ return 1;
	//~ }
	if(y[0]==1) {
		path.push_back(0);
		col=0;
		//~ cerr<<"go to: "<<col<<'\n';
		return 0;
	}
	path.push_back(1);
	col=1;
	//~ cerr<<"go to: "<<col<<'\n';
	return 1;
}

• 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