Submission #426842

#	Time	Username	Problem	Language	Result	Execution time	Memory
426842		amunduzbaev	Stray Cat (JOI20_stray)	C++14	100 / 100	90 ms	21348 KiB

Anthony

#include"bits/stdc++.h"
#include"Anthony.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
 
 
namespace sol1{
	
	vector<int> a = {0, 0, 1, 0, 1, 1};
 
	vector<pair<int,int>> e[100000];
	
	vector<int> ret;
	
	void dfs(int n, int p, int b, int k){
		//cout << n << " " << p << " " << b << " " << k << endl;
		rep(i, e[n].size()){
			if(e[n][i].first == p) continue;
			if(e[n].size() >= 3){
				if(b == 0){
					ret[e[n][i].second] = 1;
					dfs(e[n][i].first, n, 1, 2);
				}
				else{
					ret[e[n][i].second] = 0;
					dfs(e[n][i].first, n, 0, 1);
				}
			}
			if(e[n].size() == 2){
				ret[e[n][i].second] = a[(k+1)%6];
				dfs(e[n][i].first, n, a[(k+1)%6], k+1);
			}
		}
	}
	
	vector<int> Mark1(int N, int M, int A, int B, vector<int> U, vector<int> V){
		for(int i=0; i<M; i++){
			e[U[i]].push_back({V[i], i});
			e[V[i]].push_back({U[i], i});
			ret.push_back(-1);
		}
		e[0].pb({-1,-1});
		
		dfs(0, -1, 1, 0);
		rep(i, M){
			//cout << i << " " << ret[i] << endl;
		}
		return ret;
	}
	
}  // namespace
 
 
namespace sol2{
 
	vector<pair<int,int>> e[100000];
	int cost[100000];
	queue<int> que;
	vector<int> ret;
	
	vector<int> Mark2(int N, int M, int A, int B, vector<int> U, vector<int> V){
		for(int i=0; i<M; i++){
			e[U[i]].push_back({V[i], i});
			e[V[i]].push_back({U[i], i});
			ret.push_back(3);
		}
		
		for(int i=0; i<N; i++){
			cost[i] = INT_MAX;
		}
		cost[0] = 0;
		que.push(0);
		while(!que.empty()){
			int n = que.front();
			que.pop();
			for(int i=0; i<e[n].size(); i++){
				if(cost[e[n][i].first] > cost[n]+1){
					cost[e[n][i].first] = cost[n]+1;
					que.push(e[n][i].first);
				}
			}
		}
		
		for(int i=0; i<M; i++){
			if(cost[U[i]]+1 == cost[V[i]]) ret[i] = cost[U[i]] % 3;
			if(cost[U[i]] == cost[V[i]]+1) ret[i] = cost[V[i]] % 3;
			if(cost[U[i]] == cost[V[i]]) ret[i] = cost[U[i]] % 3;
		}
		
		return ret;
	}
 
}  // namespace
 
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V){
	if(A == 2) return sol1::Mark1(N, M, A, B, U, V);
	return sol2::Mark2(N, M, A, B, U, V);
}

Catherine

#include"bits/stdc++.h"
#include"Catherine.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
 
 
namespace sola{
	
	vector<int> a = {0, 0, 1, 0, 1, 1};
 
	int A, B;
	
	bool flg = false;
	vector<int> st;
	int b = -1;
	
	int Move1(vector<int> y){
		//cout <<  b << " " << flg << " " << y[0] << " " << y[1] << endl;
		if(flg){
			// -o-
			if(y[0]+y[1]+1 == 2){
				if(y[0] == 0) return b = 1;
				if(y[1] == 0) return b = 0;
			}
			// -o<
			if(y[0]+y[1]+1 > 2){
				return b = b^1;
			}
			assert(false);
		}
		
		// -o<
		if(b != -1) y[b]++;
		if(y[0]+y[1] > 2){
			flg = true;
			if(y[0] == 1){
				if(b == 0) return -1;
				return b = 0;
			}
			if(y[1] == 1){
				if(b == 1) return -1;
				return b = 1;
			}
		}
		// -o
		if(y[0] == 0 && y[1] == 1){
			flg = true;
			if(b == -1) return b = 1;
			b = 1;
			return -1;
		}
		if(y[1] == 0 && y[0] == 1){
			flg = true;
			if(b == -1) return b = 0;
			b = 0;
			return -1;
		}
		// -o-
		if(b != -1) y[b]--;
		if(b == -1){
			if(y[0] == 2){
				st.pb(0);
				st.pb(0);
				return b = 0;
			}
			if(y[1] == 2){
				st.pb(1);
				st.pb(1);
				return b = 1;
			}
			st.pb(0);
			st.pb(1);
			return b = 1;
		}
		else{
			if(y[0] == 1) st.pb(0);
			if(y[1] == 1) st.pb(1);
			if(st.size() == 5){
				flg = true;
				bool ok = true;
				rep(j, 6){
					bool same = true;
					rep(k, 5){
						same = same & (st[k] == a[(j+k)%6]);
					}
					if(same) ok = false;
				}
				//if(ok) cout << "ok" << endl;
				//else cout << "ng" << endl;
				if(ok) return b = st[4];
				else{
					b = st[3];
					//cout << "return -1" << endl;
					return -1;
				}
			}
			else{
				return b = st.back();
			}
		}
	}
 
}  // namespace
 
namespace solb{
	
	int Move2(vector<int> y){
		if(y[0] > 0 && y[1] >= 0 && y[2] == 0) return 0;
		if(y[1] > 0 && y[2] >= 0 && y[0] == 0) return 1;
		if(y[2] > 0 && y[0] >= 0 && y[1] == 0) return 2;
	}
	
}  // namespace
 
void Init(int A, int B){
	sola::A = A;
	sola::B = B;
}
 
int Move(vector<int> y){
	if(sola::A == 2) return sola::Move1(y);
	return solb::Move2(y);
}

Compilation message (stderr)

Anthony.cpp: In function 'void sol1::dfs(int, int, int, int)':
Anthony.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Anthony.cpp:22:3: note: in expansion of macro 'rep'
   22 |   rep(i, e[n].size()){
      |   ^~~
Anthony.cpp: In function 'std::vector<int> sol1::Mark1(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:9:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    9 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Anthony.cpp:50:3: note: in expansion of macro 'rep'
   50 |   rep(i, M){
      |   ^~~
Anthony.cpp: In function 'std::vector<int> sol2::Mark2(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |    for(int i=0; i<e[n].size(); i++){
      |                 ~^~~~~~~~~~~~

Catherine.cpp: In function 'int sola::Move1(std::vector<int>)':
Catherine.cpp:9:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Catherine.cpp:86:5: note: in expansion of macro 'rep'
   86 |     rep(j, 6){
      |     ^~~
Catherine.cpp:9:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    9 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
Catherine.cpp:88:6: note: in expansion of macro 'rep'
   88 |      rep(k, 5){
      |      ^~~
Catherine.cpp: In function 'int solb::Move2(std::vector<int>)':
Catherine.cpp:116:2: warning: control reaches end of non-void function [-Wreturn-type]
  116 |  }
      |  ^

• 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