oj.uz

Submission #212960

# Submission time Handle Problem Language Result Execution time Memory
212960 2020-03-24T15:51:01 Z ryansee Stray Cat (JOI20_stray) C++14
100 / 100
 358 ms 16780 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]);
	}
	if(A>2){
		vector<int> C(m),dist(n,-1);
		queue <ll> q;
		q.ph(0);
		dist[0]=0;
		while(q.size()){
			ll x=q.front(); q.pop();
			for(auto i:v[x]) if(dist[i]==-1) {
				dist[i]=dist[x]+1;
				q.ph(i);
			}
		}
		FOR(i,0,m-1){
			ll a=U[i], b=vv[i];
			if(dist[a] > dist[b]) swap(a,b);
			if(dist[a]==dist[b]) C[i]=dist[a]+1, C[i]%=3;
			else assert(dist[b]==dist[a]+1), C[i]=dist[b]%3;	
		}
		return C;
	}
	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?0: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];
		cerr<<a<<' '<<b<<' '<<C[i]<<'\n';
	}
	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) {
	::C.clear(), ::mp.clear();
	::start=1, ::A=A, ::B=B;
	FOR(i,0,5) {
		vector<int> tmp;
		DEC(j,i,i-4) tmp.pb(colour[(j+6)%6]);
		mp[tmp]=1;
	}
}

int Move(vector<int> y) {
	if(A>2){
		ll nz=0;
		FOR(i,0,A-1) if(y[i]) nz ++;
		assert(nz <= 2);
		if(nz == 1) {
			return y[0] ? 0 : (y[1] ? 1 : 2);
		}
		if(y[0] && y[1]) return 0;
		if(y[1] && y[2]) return 1;
		if(y[2] && y[0]) return 2;
		assert(0);
	}
	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) {
		if(siz(C)==1){
			gg=0, bckt=0, assert(deg==1);
			C.clear();
			return lst = (y[0]?0:1);
		}else{
			cbr;
			C.pop_back();
			assert((y[0]==1)+(y[1]==1)==1);
			return lst=(y[0]?0:1);
		}
	}
	if(gg) {// rmbr +1 to deg
		if(deg==0){
			cerr<<"no\n";
			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
				for(auto i:C) cerr<<i<<' '; cerr<<'\n';
				if(mp[C]){// correct
					gg=0;
					C.clear();
					return lst=(y[0]?0:1);
				}else{
					bckt=1;
					C.pop_back(), C.pop_back();
					cerr<<"flip\n";
					return lst=-1;
				}
			}
		}else { // deg + 1 > 2
			if(y[0]==0||y[1]==0){// wrong
				bckt=1;
				C.pop_back();
				cerr<<y[0]<<' '<<y[1]<<'\n';
				return lst=-1;
			}else{
				gg=0;
				C.clear();
			}
		}
	}
	assert(lst!=-1);
	ll zero=y[0],one=y[1];
	lst ? ++ one : ++ zero;
	if(one==1&&zero==1){
		lst ^= 1; return lst;
	}
	if(min(one,zero)==0){
		return lst;
	}
	if(zero == 1 || one == 1); else assert(0);
	if(zero==1) { return lst=0; }
	else { return lst=1; }
}
/*
7 6 2 6 4
0 2
0 4
1 2
1 3
1 5
4 6
*/

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:100:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
     ^~~
Catherine.cpp:100:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
                                 ^~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15680 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 60 ms 15076 KB Output is correct
4 Correct 84 ms 16780 KB Output is correct
5 Correct 80 ms 16684 KB Output is correct
6 Correct 57 ms 15348 KB Output is correct
7 Correct 57 ms 15436 KB Output is correct
8 Correct 76 ms 16196 KB Output is correct
9 Correct 75 ms 16204 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 15680 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 60 ms 15076 KB Output is correct
4 Correct 84 ms 16780 KB Output is correct
5 Correct 80 ms 16684 KB Output is correct
6 Correct 57 ms 15348 KB Output is correct
7 Correct 57 ms 15436 KB Output is correct
8 Correct 76 ms 16196 KB Output is correct
9 Correct 75 ms 16204 KB Output is correct
10 Correct 53 ms 13304 KB Output is correct
11 Correct 61 ms 13424 KB Output is correct
12 Correct 54 ms 13424 KB Output is correct
13 Correct 55 ms 13296 KB Output is correct
14 Correct 62 ms 13760 KB Output is correct
15 Correct 66 ms 14048 KB Output is correct
16 Correct 72 ms 16244 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13436 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 48 ms 12640 KB Output is correct
4 Correct 74 ms 14540 KB Output is correct
5 Correct 79 ms 14456 KB Output is correct
6 Correct 54 ms 13116 KB Output is correct
7 Correct 54 ms 13292 KB Output is correct
8 Correct 75 ms 13820 KB Output is correct
9 Correct 67 ms 13940 KB Output is correct
10 Correct 68 ms 13524 KB Output is correct
11 Correct 64 ms 13496 KB Output is correct
12 Correct 66 ms 13684 KB Output is correct
13 Correct 72 ms 13636 KB Output is correct
14 Correct 81 ms 13812 KB Output is correct
15 Correct 92 ms 13892 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13436 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 48 ms 12640 KB Output is correct
4 Correct 74 ms 14540 KB Output is correct
5 Correct 79 ms 14456 KB Output is correct
6 Correct 54 ms 13116 KB Output is correct
7 Correct 54 ms 13292 KB Output is correct
8 Correct 75 ms 13820 KB Output is correct
9 Correct 67 ms 13940 KB Output is correct
10 Correct 68 ms 13524 KB Output is correct
11 Correct 64 ms 13496 KB Output is correct
12 Correct 66 ms 13684 KB Output is correct
13 Correct 72 ms 13636 KB Output is correct
14 Correct 81 ms 13812 KB Output is correct
15 Correct 92 ms 13892 KB Output is correct
16 Correct 58 ms 11636 KB Output is correct
17 Correct 62 ms 11612 KB Output is correct
18 Correct 54 ms 11516 KB Output is correct
19 Correct 51 ms 11624 KB Output is correct
20 Correct 71 ms 12284 KB Output is correct
21 Correct 59 ms 11888 KB Output is correct
22 Correct 64 ms 14076 KB Output is correct
23 Correct 51 ms 11520 KB Output is correct
24 Correct 55 ms 11632 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1792 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 16 ms 1792 KB Output is correct
4 Correct 20 ms 1744 KB Output is correct
5 Correct 16 ms 1896 KB Output is correct
6 Correct 18 ms 1792 KB Output is correct
7 Correct 18 ms 1744 KB Output is correct
8 Correct 21 ms 1792 KB Output is correct
9 Correct 16 ms 1792 KB Output is correct
10 Correct 16 ms 1792 KB Output is correct
11 Correct 17 ms 1792 KB Output is correct
12 Correct 16 ms 1792 KB Output is correct
13 Correct 17 ms 1792 KB Output is correct
14 Correct 18 ms 1792 KB Output is correct
15 Correct 17 ms 1792 KB Output is correct
16 Correct 20 ms 1936 KB Output is correct
17 Correct 17 ms 1792 KB Output is correct
18 Correct 20 ms 1792 KB Output is correct
19 Correct 18 ms 1792 KB Output is correct
20 Correct 16 ms 1792 KB Output is correct
21 Correct 20 ms 1792 KB Output is correct
22 Correct 18 ms 1792 KB Output is correct
23 Correct 20 ms 1792 KB Output is correct
24 Correct 18 ms 1792 KB Output is correct
25 Correct 19 ms 1792 KB Output is correct
26 Correct 20 ms 1792 KB Output is correct
27 Correct 20 ms 1792 KB Output is correct
28 Correct 17 ms 1792 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 11836 KB Output is correct
2 Correct 317 ms 13460 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 302 ms 11568 KB Output is correct
5 Correct 329 ms 15616 KB Output is correct
6 Correct 317 ms 15756 KB Output is correct
7 Correct 301 ms 14848 KB Output is correct
8 Correct 324 ms 14696 KB Output is correct
9 Correct 335 ms 15588 KB Output is correct
10 Correct 319 ms 15664 KB Output is correct
11 Correct 309 ms 15772 KB Output is correct
12 Correct 295 ms 15668 KB Output is correct
13 Correct 302 ms 15580 KB Output is correct
14 Correct 332 ms 15612 KB Output is correct
15 Correct 332 ms 15644 KB Output is correct
16 Correct 319 ms 15740 KB Output is correct
17 Correct 339 ms 15264 KB Output is correct
18 Correct 313 ms 15328 KB Output is correct
19 Correct 323 ms 15420 KB Output is correct
20 Correct 308 ms 15220 KB Output is correct
21 Correct 331 ms 15344 KB Output is correct
22 Correct 309 ms 15216 KB Output is correct
23 Correct 302 ms 11656 KB Output is correct
24 Correct 302 ms 11688 KB Output is correct
25 Correct 296 ms 12336 KB Output is correct
26 Correct 284 ms 12388 KB Output is correct
27 Correct 315 ms 13552 KB Output is correct
28 Correct 315 ms 13556 KB Output is correct
29 Correct 314 ms 13552 KB Output is correct
30 Correct 297 ms 13600 KB Output is correct
31 Correct 295 ms 11628 KB Output is correct
32 Correct 303 ms 11584 KB Output is correct
33 Correct 308 ms 12184 KB Output is correct
34 Correct 305 ms 12352 KB Output is correct
35 Correct 325 ms 13372 KB Output is correct
36 Correct 311 ms 13408 KB Output is correct
37 Correct 321 ms 13380 KB Output is correct
38 Correct 296 ms 13456 KB Output is correct
39 Correct 312 ms 13436 KB Output is correct
40 Correct 320 ms 13304 KB Output is correct
41 Correct 328 ms 14532 KB Output is correct
42 Correct 332 ms 14340 KB Output is correct
43 Correct 319 ms 14876 KB Output is correct
44 Correct 319 ms 14812 KB Output is correct
45 Correct 323 ms 14784 KB Output is correct
46 Correct 345 ms 14864 KB Output is correct
47 Correct 308 ms 13100 KB Output is correct
48 Correct 316 ms 13200 KB Output is correct
49 Correct 335 ms 13120 KB Output is correct
50 Correct 313 ms 13332 KB Output is correct
51 Correct 296 ms 11756 KB Output is correct
52 Correct 287 ms 12144 KB Output is correct
53 Correct 267 ms 11896 KB Output is correct
54 Correct 333 ms 11912 KB Output is correct
55 Correct 290 ms 11772 KB Output is correct
56 Correct 299 ms 11896 KB Output is correct
57 Correct 286 ms 11828 KB Output is correct
58 Correct 313 ms 11768 KB Output is correct
59 Correct 305 ms 11948 KB Output is correct
60 Correct 319 ms 11888 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 11728 KB Output is correct
2 Correct 293 ms 13296 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 326 ms 11424 KB Output is correct
5 Correct 321 ms 15720 KB Output is correct
6 Correct 349 ms 15580 KB Output is correct
7 Correct 318 ms 14820 KB Output is correct
8 Correct 322 ms 14872 KB Output is correct
9 Correct 340 ms 15560 KB Output is correct
10 Correct 322 ms 15664 KB Output is correct
11 Correct 306 ms 15660 KB Output is correct
12 Correct 286 ms 15700 KB Output is correct
13 Correct 328 ms 15688 KB Output is correct
14 Correct 329 ms 15728 KB Output is correct
15 Correct 320 ms 15768 KB Output is correct
16 Correct 335 ms 15692 KB Output is correct
17 Correct 320 ms 15408 KB Output is correct
18 Correct 343 ms 15312 KB Output is correct
19 Correct 295 ms 15240 KB Output is correct
20 Correct 294 ms 15344 KB Output is correct
21 Correct 330 ms 15172 KB Output is correct
22 Correct 321 ms 15252 KB Output is correct
23 Correct 358 ms 11560 KB Output is correct
24 Correct 304 ms 11656 KB Output is correct
25 Correct 329 ms 12388 KB Output is correct
26 Correct 282 ms 12288 KB Output is correct
27 Correct 300 ms 13552 KB Output is correct
28 Correct 327 ms 13560 KB Output is correct
29 Correct 291 ms 13552 KB Output is correct
30 Correct 341 ms 13552 KB Output is correct
31 Correct 291 ms 11612 KB Output is correct
32 Correct 314 ms 11724 KB Output is correct
33 Correct 300 ms 12152 KB Output is correct
34 Correct 312 ms 12476 KB Output is correct
35 Correct 301 ms 13332 KB Output is correct
36 Correct 314 ms 13432 KB Output is correct
37 Correct 298 ms 13264 KB Output is correct
38 Correct 317 ms 13448 KB Output is correct
39 Correct 338 ms 13376 KB Output is correct
40 Correct 301 ms 13420 KB Output is correct
41 Correct 306 ms 14348 KB Output is correct
42 Correct 315 ms 14260 KB Output is correct
43 Correct 315 ms 14372 KB Output is correct
44 Correct 328 ms 14400 KB Output is correct
45 Correct 306 ms 14540 KB Output is correct
46 Correct 304 ms 14296 KB Output is correct
47 Correct 305 ms 13048 KB Output is correct
48 Correct 303 ms 13100 KB Output is correct
49 Correct 326 ms 13084 KB Output is correct
50 Correct 324 ms 13152 KB Output is correct
51 Correct 304 ms 11816 KB Output is correct
52 Correct 318 ms 11744 KB Output is correct
53 Correct 301 ms 11888 KB Output is correct
54 Correct 316 ms 11860 KB Output is correct
55 Correct 292 ms 11864 KB Output is correct
56 Correct 303 ms 11768 KB Output is correct
57 Correct 292 ms 11872 KB Output is correct
58 Correct 299 ms 11764 KB Output is correct
59 Correct 309 ms 11792 KB Output is correct
60 Correct 294 ms 11748 KB Output is correct