Submission #829667

#	Time	Username	Problem	Language	Result	Execution time	Memory
829667		MODDI	Stray Cat (JOI20_stray)	C++14	85 / 100	38 ms	15100 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
namespace {
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
 	vi arr(M, -1);
 	vector<vector<pii>> G(N, vector<pii>());
 	for(int i = 0; i < M; i++){
 		int u = U[i], v = V[i];
 		G[u].pb({v, i});
 		G[v].pb({u, i});
	 }
	vi dist(N, N);
	dist[0] = 0;
	queue<int> q;
	q.push(0);
	vi ord;
	while(!q.empty()){
		int v = q.front();
		ord.pb(v);
		q.pop();
		for(pii next : G[v]){
			if(dist[next.first] == N){
				dist[next.first] = 1 + dist[v];
				q.push(next.first);
			}
		}
	}
	if(A >= 3){
		for(int i = 0; i < M; i++){
			arr[i] = min(dist[U[i]], dist[V[i]]) % 3;
		}
		return arr;
	}
	else{
		vi pib(N, -1);
		for(int i = 0; i < N; i++){
			int v = ord[i];
			if(i == 0){
				for(auto t : G[v]){
					arr[t.second] = 0;
				}
				continue;
			}
			int deg = (int) G[v].size();
			if(deg == 1)	continue;
			int par = -1, parC = -1;
			for(auto t : G[v]){
				if(dist[t.first] < dist[v]){
					par = t.first;
					parC = arr[t.second];
				}
			}
			if(deg == 2){
				if(pib[par] != -1){
					pib[v] = (pib[par] + 1) % 6;
				}
				else
					pib[v] = parC + 1;
				int col = (pib[v] == 0 || pib[v] == 2 || pib[v] == 3 ? 0 : 1);
				for(auto t : G[v]){
					if(t.first != par)
						arr[t.second] = col;
				}
			}
			else{
				for(auto t : G[v]){
					if(t.first != par)
						arr[t.second] = parC ^ 1;
				}
			}
			
		}
	}
	
	return arr;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
namespace {
 
int A;
bool bP;
vector<int> colors;
 
bool Uping(vector<int> s) {
  vector<int> t = {1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0};
//  reverse(t.begin(), t.end());
  for (int i = 0; i + (int)s.size() <= (int)t.size(); i++) {
    bool ok = true;
    for (int j = 0; j < (int)s.size(); j++)
      ok &= s[j] == t[i + j];
    if (ok) return true;
  }
  return false;
}
 
}  // namespace
 
void Init(int A, int B) {
  A = A;
  bP = true;
  colors = vector<int>();
}
 
int Move(std::vector<int> y) {
	if (A > 2) {
		int c = 0;
	    while(c < 3) {
	      if (y[c] > 0 && y[(c + 2) % 3] == 0) break;
	      c++;
	    }
	    return c;
	  } 
	else{
		if(!colors.empty())	y[colors.back()]++;
		int deg = y[0] + y[1], col = -2;
		if(deg == 1){
			bP = false;
			if(colors.empty())	col = (y[0] > 0 ? 0 : 1);
			else col = -1;
		}
		else if (deg == 2) {
     		if (!bP) {
       			y[colors.back()]--;
        		col = (y[0] > 0 ? 0 : 1);
      		} 
		    else {
		        if ((int)colors.size() < 4) {
		          	if (!colors.empty()) y[colors.back()]--;
		         	col = (y[0] > 0 ? 0 : 1);
		         	if (colors.empty()) {
		            	y[col]--;
		            	colors.push_back((y[0] > 0 ? 0 : 1));
		         	}
	        	} 
				else {
			        y[colors.back()]--;
			        col = (y[0] > 0 ? 0 : 1);
			        vector<int> s = colors;
			    	s.push_back(col);
			        if (!Uping(s)) col = -1;
			        bP = false;
	        	}
	      	}
    	} 
		else {
		    bP = false;
		    col = (y[0] == 1 ? 0 : 1);
		    if (!colors.empty() && colors.back() == col) col = -1;
    	}
	    if (col == -1) {
	      int x = colors.back();
	      colors.push_back(x^1);
	    } else {
	      colors.push_back(col);
	    }
    return col;
  	}	
}

• 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