Submission #1183196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183196		mertbbm	Stray Cat (JOI20_stray)	C++20	0 / 100	26 ms	12352 KiB

Anthony

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

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

namespace{
	vector<pii>adj[200005];
	vector<int>ret;
	int s2[6]={0,0,1,1,0,1};
	
	void dfs(int index, int par, int cur, bool amos){
		//cerr << index << " " << amos << " visit" << endl;
		for(auto it:adj[index]){
			if(it.first==par) continue;
			if(adj[index].size()>2){
				if(amos){
					//place 0
					//cerr << it.second << " it.second" << endl; 
					ret[it.second]=0;
					dfs(it.first,index,1,0);
				}
				else{
					//place 1 
					//cerr << it.second << " 1it.second" << endl;
					ret[it.second]=1;
					dfs(it.first,index,0,1);
				}
			}
			else{
				ret[it.second]=s2[cur%6];
				dfs(it.first,index,(cur+1)%6,ret[it.second]);
			}
		}
	}
	
	struct DSU{
		vector<int>e;
		void init(int n){
			e=vector<int>(n,-1);
		}
		
		int get(int x){
			return e[x]<0?x:e[x]=get(e[x]);
		}
		
		bool unite(int x, int y){
			x=get(x); y=get(y);
			if(x==y) return 1;
			if(e[x]>e[y]) swap(x,y);
			e[x]+=e[y];
			e[y]=x;
			return 0;
		}
	};
}

vector<int>Mark(int n, int m, int a, int b, vector<int>u, vector<int>v){
	::ret.resize(m,-1);
	::DSU dsu;
	dsu.init(n+5);
	for(int x=0;x<m;x++){
		if(dsu.unite(u[x],v[x])){
			ret[x]=2;
			continue;
		}
		::adj[u[x]].push_back({v[x],x});
		::adj[v[x]].push_back({u[x],x});
	}

	::dfs(0,-1,0,1);
	//cerr << "done" << endl;
	//for(int y=0;y<(int)::ret.size();y++){
		//cout << ::ret[y] << " ";
	//}
	//cout << "\n";
	return ::ret;
}

Catherine

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

//#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

namespace{
	int color=0;
	int s[6]={1,0,1,1,0,0};
	vector<int>cur;
	bool amos=true;
}

void Init(int A, int B){
	::color=A;
}

int Move(vector<int>y){
	int deg=0;
	vector<int>v;
	for(int x=0;x<2;x++){
		deg+=y[x];
		for(int i=0;i<y[x];i++) v.push_back(x);
	}
	if(!::cur.empty()) deg++;
	if(::cur.empty()){
		if(deg!=2) ::amos=false;
		if(y[1]){
			::cur.push_back(1);
			return 1;
		}
		else{
			::cur.push_back(0);
			return 0;
		}
	}
	//show(deg,deg);
	//show4(cur,::cur);
	
	if(deg==1){
		::amos=false;
		return -1;
	}
	if(deg>2){
		::amos=false;
		if(!y[::cur.back()]) return -1;
		else{
			::cur.push_back(!::cur.back());
			return ::cur.back();
		}
	}
	else if(!amos){
		if(y[0]) return 0;
		else return 1;
	}
	else{
		//show4(v,v);
		for(auto it:v){
			::cur.push_back(it);
			//show4(cur,::cur);
			if(::cur.size()==5){
				bool valid=false;
				for(int y=0;y<6;y++){
					bool ok=true;
					for(int i=0;i<5;i++){
						if(s[(y+i)%6]!=::cur[i]) ok=false;
					}
					valid|=ok;
				}
				::amos=false;
				if(!valid){
					return -1;
					::cur.pop_back();
				}
			}
			return ::cur.back();
		}
	}
	return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 2
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 71
• Subtask 7: 0 / 9