oj.uz

Submission #212913

# Submission time Handle Problem Language Result Execution time Memory
212913 2020-03-24T13:54:56 Z ryansee Stray Cat (JOI20_stray) C++14
0 / 100
 96 ms 22096 KB 
#include "Anthony.h"
#include "bits/stdc++.h"
using namespace std;

namespace {

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
vector<int> v[MAXN];
// RRBRBB
int colour[] = {0, 0, 1, 0, 1, 1};
}  // namespace

vector<int> Mark(int n, int m, int A, int B,vector<int> U, vector<int> vv) {
	FOR(i,0,m-1){
		v[U[i]].eb(vv[i]), v[vv[i]].eb(U[i]);
	}
	vector<int> C(m);
	vector<bool> V(n);
	vector<int> depth(n,0);
	function<void(ll,ll,ll)>dfs=[&](ll x,ll p,ll c){
		V[x]=colour[c];
		if(siz(v[x])-(p!=x) == 1){ // line
			if(v[x][0]==p) v[x].erase(v[x].begin());
			depth[v[x][0]]=depth[x]+1, dfs(v[x][0], x, (c+1)%6);
		}else{
			for(auto i:v[x])if(i^p){
				depth[i]=depth[x]+1, dfs(i,x,(V[x]==1?1:2));
			}
		}
	};
	dfs(0,0,0);
	FOR(i,0,m-1){ll a=U[i],b=vv[i];
		if(depth[a]<depth[b])swap(a,b);
		C[i]=V[a];
	}
	return C;
}

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

namespace {

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
ll A, B, start, lst=-1, gg=0, bckt=0;
vector<int> C;
map<vector<int>,bool> mp;
// int colour[] = {0, 0, 1, 0, 1, 1};
}  // namespace

void Init(int A, int B) {
	start=1, ::A=A, ::B=B;
	mp[{0,0,1,0,1,1}]=mp[{0,1,0,1,1,0}]=mp[{1,0,1,1,0,0}]=mp[{0,1,1,0,0,1}]=mp[{1,1,0,0,1,0}]=mp[{1,0,0,1,0,1}]=1;
}

int Move(vector<int> y) {
	int deg=accumulate(all(y), 0ll);
	if(start){
		start=0;
		assert(deg>0);
		if(deg==1){
			lst=y[0]?0:1;
			return lst;
		}else if(deg==2){
			gg=1;
			FOR(i,0,1) FOR(j,1,y[i]) C.pb(i);
			return lst=(y[1]?1:0);
		}else{ // >2
			assert(y[0]==1||y[1]==1); 
			return lst = (y[0]==1 ? 0 : 1);
		}
	}
	if(bckt) { assert(lst==-1);
		if(siz(C)==1){
			gg=0, bckt=0, assert(deg==1);
			C.clear();
			return lst = (y[0]?0:1);
		}else{
			C.pop_back();
			return lst=-1;
		}
	}
	if(gg) {// rmbr +1 to deg
		if(deg==0){
			C.pop_back();bckt=1;
			return lst=-1;
		}else if(deg==1){
			if(y[0]) C.pb(0); else C.pb(1);
			if(siz(C)<5){
				return lst=(y[0]?0:1);
			}else{assert(siz(C)==5); // pop 2
				if(mp[C]){// correct
					gg=0;
					C.clear();
					return lst=(y[0]?0:1);
				}else{
					bckt=1;
					C.pop_back(), C.pop_back();
					return lst=-1;
				}
			}
		}else { // deg + 1 > 2
			if(y[0]==0||y[1]==0){// wrong
				bckt=1;
				C.pop_back();
				return lst=-1;
			}else{
				gg=0;
				ll zero=y[0]+(lst==0),one=y[1]+(lst==1);
				assert(zero==1||one==1);
				return lst=(zero==1?0:1);
			}
		}
	}
	ll zero=y[0],one=y[1];
	lst ? ++ one : ++ zero;
	if(one==1&&zero==1){
		lst ^= 1; return lst;
	}
	if(max(zero,one)==2&&min(one,zero)==0){
		return lst;
	}
	if(zero==1)return lst=0;
	else return lst=1;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17360 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 47 ms 15124 KB Output is correct
4 Correct 82 ms 19540 KB Output is correct
5 Incorrect 84 ms 19528 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 17360 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 47 ms 15124 KB Output is correct
4 Correct 82 ms 19540 KB Output is correct
5 Incorrect 84 ms 19528 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14912 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 56 ms 12932 KB Output is correct
4 Correct 80 ms 17112 KB Output is correct
5 Incorrect 66 ms 17120 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14912 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 56 ms 12932 KB Output is correct
4 Correct 80 ms 17112 KB Output is correct
5 Incorrect 66 ms 17120 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 17 ms 1536 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 10 ms 1792 KB Output is correct
5 Correct 10 ms 1792 KB Output is correct
6 Correct 10 ms 1792 KB Output is correct
7 Incorrect 11 ms 1792 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11624 KB Output is correct
2 Correct 58 ms 13472 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 50 ms 11364 KB Output is correct
5 Correct 96 ms 15720 KB Output is correct
6 Correct 66 ms 15592 KB Output is correct
7 Incorrect 54 ms 14664 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11660 KB Output is correct
2 Runtime error 57 ms 22096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -