oj.uz

Submission #522110

# Submission time Handle Problem Language Result Execution time Memory
522110 2022-02-03T20:54:09 Z new_acc Stray Cat (JOI20_stray) C++14
100 / 100
 53 ms 17876 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < int(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int NN=2e4+10;
int deg[NN],kol[NN],kt[NN];
bool vis[NN];
vi graf[NN],num[NN];
void bfs(){
	deque<int> deq;
	deq.push_back(0),vis[0]=1;
	while(deq.size()){
		int v=deq.front();
		deq.pop_front();
		for(auto u:graf[v]){
			if(!vis[u]){
				deg[u]=deg[v]+1,vis[u]=1;
				deq.push_back(u);
			}
		}
	}
}
void dfs(int v,int o,int pop=1){
	string s="010011";
	if(graf[v].size()>2 or graf[v].size()==1){
		rep(i,graf[v].size()){
			if(graf[v][i]==o) continue;
			kol[num[v][i]]=(pop+1)%2;
		}
	}else{
		if(kt[o]==0 and pop==1) kt[v]=0;
		else kt[v]=(kt[o]+1)%(int)(s.size());
		rep(i,graf[v].size()){
			if(graf[v][i]==o) continue;
			kol[num[v][i]]=int(s[kt[v]])-48;
		}
	}
	rep(i,graf[v].size()){
		int u=graf[v][i];
		if(u==o) continue;
		dfs(u,v,kol[num[v][i]]);
	}
}
vi Mark(int n,int m,int a,int b,vi u,vi v){
	rep(i,m) graf[u[i]].push_back(v[i]),graf[v[i]].push_back(u[i]),num[u[i]].push_back(i),num[v[i]].push_back(i);
	if(b==0){
		bfs();
		rep(i,n) kol[i]=(i==0?0:(kol[i-1]+1)%3);
		vi res;
		rep(i,m) res.push_back(kol[min(deg[u[i]],deg[v[i]])]);
		return res;
	}
	vi wyn;
	dfs(0,0);
	rep(i,m) wyn.push_back(kol[i]);
	return wyn;
}
/*int main(){
	int n,m;
	cin>>n>>m;
	vi v,u;
	rep(i,m){
		int a,b;
		cin>>a>>b;
		v.push_back(a),u.push_back(b);
	}
	vi wyn=Mark(n,m,2,6,v,u);
	for(auto u:wyn) cout<<u<<"\n";
}*/
#include "Catherine.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e4+10;
int il;
bool strona=0;
int ru=0,pocz=-1,pop=0;
bool znal;
string s;
string og="010011";
string d1="01001",d2="10011",d3="00110",d4="01101",d5="11010",d6="10100";
vi akt;
void Init(int a,int b){
	il=a;
}
int Move(vi t){
	if(il>=3){
		bool c[3];
		c[0]=c[1]=c[2]=0;
		rep(i,t.size()) c[i]=(t[i]>0?1:0);
		if(c[0]>0 and c[1]>0) return 0;
		if(c[1]>0 and c[2]>0) return 1;
		if(c[2]>0 and c[0]>0) return 2;
		if(c[0]) return 0;
		if(c[1]) return 1;
		return 2;
	}
	if(pocz==-1){
		pocz=1;
		if(t[0] and t[1]){
			if(t[0]+t[1]>2){
				strona=1;
				if(t[0]==1){pop=0;return 0;}
				pop=1;
				return 1;
			}
			akt.push_back(0);
			s+='1',s+='0';
			pop=0;
			return 0;
		}else{
			if(t[0]==1 or t[1]==1){
				strona=1;
				if(t[0]) {pop=0;return 0;}
				pop=1;
				return 1;
			}else{
				if(t[0]){
					s+='0';
					s+='0';
					pop=0;
					akt.push_back(0);
					return 0;
				}else{
					s+='1';
					s+='1';
					pop=1;
					akt.push_back(1);
					return 1;
				}
			}
		}
	}else{
		if(strona){
			if(t[0] and t[1]){
				(pop+=1)%=2;
				return pop;
			}else{
				if(t[0]){pop=0;return 0;}
				pop=1;
				return 1;
			}
		}else{
			if((int)akt.size()==0){
				strona=1;
				pop=(t[0]>0?0:1);
				return pop;
			}
			if(znal){
				int lo=akt.back();
				akt.pop_back();
				return lo;
			}
			if((t[0]>1 and !t[1]) or (t[1]>1 and !t[0]) or (!t[0] and !t[1])) znal=1;
			if(znal){akt.pop_back();return -1;}
			if(t[0] and t[1]){
				strona=1;
				(pop+=1)%=2;
				return pop;
			}
			if((int)akt.size()==3){
				if(t[0]) s+='0';
				if(t[1]) s+='1';
				if(s==d1 or s==d2 or s==d3 or s==d4 or s==d5 or s==d6){
					znal=1;
					akt.pop_back();
					return -1;
				}else{
					strona=1;
					if(t[0]) pop=0;
					else pop=1;
					return pop;
				}
			}
			if(t[0]) pop=0,s+='0';
			else pop=1,s+='1';
			akt.push_back(pop);
			return pop;
		}
	}
}
/*int main(){
	vector<int> v;
	v.push_back(1),v.push_back(1);
	cout<<Move(v)<<"\n";
	v[1]=1,v[0]=0;
	cout<<Move(v)<<"\n";
	v[0]=1,v[1]=0;
	cout<<Move(v)<<"\n";
	cout<<Move(v)<<"\n";
	v[0]=0,v[1]=1;
	cout<<Move(v)<<"\n";
	return 0;
	v[0]=1,v[1]=0;
	cout<<Move(v)<<"\n";	
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16676 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 31 ms 15976 KB Output is correct
4 Correct 46 ms 17744 KB Output is correct
5 Correct 47 ms 17876 KB Output is correct
6 Correct 37 ms 16480 KB Output is correct
7 Correct 37 ms 16540 KB Output is correct
8 Correct 44 ms 17248 KB Output is correct
9 Correct 47 ms 17132 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16676 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 31 ms 15976 KB Output is correct
4 Correct 46 ms 17744 KB Output is correct
5 Correct 47 ms 17876 KB Output is correct
6 Correct 37 ms 16480 KB Output is correct
7 Correct 37 ms 16540 KB Output is correct
8 Correct 44 ms 17248 KB Output is correct
9 Correct 47 ms 17132 KB Output is correct
10 Correct 34 ms 14304 KB Output is correct
11 Correct 34 ms 14472 KB Output is correct
12 Correct 34 ms 14324 KB Output is correct
13 Correct 33 ms 14436 KB Output is correct
14 Correct 33 ms 14620 KB Output is correct
15 Correct 39 ms 14996 KB Output is correct
16 Correct 42 ms 17212 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14212 KB Output is correct
2 Correct 1 ms 1512 KB Output is correct
3 Correct 30 ms 13852 KB Output is correct
4 Correct 45 ms 15656 KB Output is correct
5 Correct 46 ms 15536 KB Output is correct
6 Correct 34 ms 14312 KB Output is correct
7 Correct 34 ms 14304 KB Output is correct
8 Correct 41 ms 14896 KB Output is correct
9 Correct 46 ms 14980 KB Output is correct
10 Correct 40 ms 14636 KB Output is correct
11 Correct 38 ms 14684 KB Output is correct
12 Correct 38 ms 14720 KB Output is correct
13 Correct 38 ms 14696 KB Output is correct
14 Correct 40 ms 15040 KB Output is correct
15 Correct 41 ms 15048 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14212 KB Output is correct
2 Correct 1 ms 1512 KB Output is correct
3 Correct 30 ms 13852 KB Output is correct
4 Correct 45 ms 15656 KB Output is correct
5 Correct 46 ms 15536 KB Output is correct
6 Correct 34 ms 14312 KB Output is correct
7 Correct 34 ms 14304 KB Output is correct
8 Correct 41 ms 14896 KB Output is correct
9 Correct 46 ms 14980 KB Output is correct
10 Correct 40 ms 14636 KB Output is correct
11 Correct 38 ms 14684 KB Output is correct
12 Correct 38 ms 14720 KB Output is correct
13 Correct 38 ms 14696 KB Output is correct
14 Correct 40 ms 15040 KB Output is correct
15 Correct 41 ms 15048 KB Output is correct
16 Correct 30 ms 12660 KB Output is correct
17 Correct 31 ms 12616 KB Output is correct
18 Correct 31 ms 12624 KB Output is correct
19 Correct 32 ms 12600 KB Output is correct
20 Correct 38 ms 13008 KB Output is correct
21 Correct 38 ms 12856 KB Output is correct
22 Correct 40 ms 15120 KB Output is correct
23 Correct 34 ms 12676 KB Output is correct
24 Correct 33 ms 12744 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1780 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 2 ms 1780 KB Output is correct
5 Correct 2 ms 1780 KB Output is correct
6 Correct 2 ms 1780 KB Output is correct
7 Correct 3 ms 1772 KB Output is correct
8 Correct 2 ms 1772 KB Output is correct
9 Correct 2 ms 1780 KB Output is correct
10 Correct 2 ms 1848 KB Output is correct
11 Correct 3 ms 1776 KB Output is correct
12 Correct 2 ms 1780 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1776 KB Output is correct
15 Correct 2 ms 1772 KB Output is correct
16 Correct 2 ms 1784 KB Output is correct
17 Correct 2 ms 1784 KB Output is correct
18 Correct 2 ms 1788 KB Output is correct
19 Correct 2 ms 1772 KB Output is correct
20 Correct 2 ms 1784 KB Output is correct
21 Correct 2 ms 1784 KB Output is correct
22 Correct 2 ms 1784 KB Output is correct
23 Correct 2 ms 1784 KB Output is correct
24 Correct 2 ms 1784 KB Output is correct
25 Correct 2 ms 1784 KB Output is correct
26 Correct 2 ms 1784 KB Output is correct
27 Correct 2 ms 1776 KB Output is correct
28 Correct 2 ms 1784 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12512 KB Output is correct
2 Correct 37 ms 14044 KB Output is correct
3 Correct 1 ms 1520 KB Output is correct
4 Correct 31 ms 12184 KB Output is correct
5 Correct 43 ms 15732 KB Output is correct
6 Correct 43 ms 15792 KB Output is correct
7 Correct 37 ms 14896 KB Output is correct
8 Correct 39 ms 15228 KB Output is correct
9 Correct 47 ms 16104 KB Output is correct
10 Correct 45 ms 16116 KB Output is correct
11 Correct 45 ms 16176 KB Output is correct
12 Correct 41 ms 16124 KB Output is correct
13 Correct 41 ms 16168 KB Output is correct
14 Correct 40 ms 16104 KB Output is correct
15 Correct 41 ms 16288 KB Output is correct
16 Correct 40 ms 16096 KB Output is correct
17 Correct 38 ms 15864 KB Output is correct
18 Correct 39 ms 15944 KB Output is correct
19 Correct 39 ms 15948 KB Output is correct
20 Correct 45 ms 15844 KB Output is correct
21 Correct 39 ms 15748 KB Output is correct
22 Correct 38 ms 15844 KB Output is correct
23 Correct 32 ms 12960 KB Output is correct
24 Correct 32 ms 12900 KB Output is correct
25 Correct 33 ms 13404 KB Output is correct
26 Correct 34 ms 13548 KB Output is correct
27 Correct 39 ms 14532 KB Output is correct
28 Correct 39 ms 14616 KB Output is correct
29 Correct 37 ms 14616 KB Output is correct
30 Correct 39 ms 14568 KB Output is correct
31 Correct 32 ms 12920 KB Output is correct
32 Correct 33 ms 12984 KB Output is correct
33 Correct 40 ms 13420 KB Output is correct
34 Correct 35 ms 13468 KB Output is correct
35 Correct 38 ms 14392 KB Output is correct
36 Correct 37 ms 14364 KB Output is correct
37 Correct 37 ms 14392 KB Output is correct
38 Correct 39 ms 14368 KB Output is correct
39 Correct 38 ms 14328 KB Output is correct
40 Correct 37 ms 14320 KB Output is correct
41 Correct 53 ms 15080 KB Output is correct
42 Correct 48 ms 15100 KB Output is correct
43 Correct 39 ms 15208 KB Output is correct
44 Correct 39 ms 15108 KB Output is correct
45 Correct 39 ms 15116 KB Output is correct
46 Correct 40 ms 15216 KB Output is correct
47 Correct 37 ms 14080 KB Output is correct
48 Correct 39 ms 14208 KB Output is correct
49 Correct 37 ms 13972 KB Output is correct
50 Correct 37 ms 14216 KB Output is correct
51 Correct 34 ms 13080 KB Output is correct
52 Correct 34 ms 13208 KB Output is correct
53 Correct 33 ms 13012 KB Output is correct
54 Correct 33 ms 13072 KB Output is correct
55 Correct 33 ms 13016 KB Output is correct
56 Correct 39 ms 13088 KB Output is correct
57 Correct 41 ms 13140 KB Output is correct
58 Correct 35 ms 13208 KB Output is correct
59 Correct 33 ms 13096 KB Output is correct
60 Correct 33 ms 13104 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12944 KB Output is correct
2 Correct 36 ms 14348 KB Output is correct
3 Correct 1 ms 1504 KB Output is correct
4 Correct 30 ms 12744 KB Output is correct
5 Correct 42 ms 16144 KB Output is correct
6 Correct 42 ms 16108 KB Output is correct
7 Correct 35 ms 15300 KB Output is correct
8 Correct 36 ms 15296 KB Output is correct
9 Correct 43 ms 16164 KB Output is correct
10 Correct 49 ms 16404 KB Output is correct
11 Correct 41 ms 16156 KB Output is correct
12 Correct 41 ms 16084 KB Output is correct
13 Correct 41 ms 16172 KB Output is correct
14 Correct 41 ms 16136 KB Output is correct
15 Correct 48 ms 16152 KB Output is correct
16 Correct 46 ms 16124 KB Output is correct
17 Correct 44 ms 15840 KB Output is correct
18 Correct 39 ms 15832 KB Output is correct
19 Correct 41 ms 15896 KB Output is correct
20 Correct 39 ms 15856 KB Output is correct
21 Correct 40 ms 15900 KB Output is correct
22 Correct 39 ms 15852 KB Output is correct
23 Correct 42 ms 12916 KB Output is correct
24 Correct 36 ms 12932 KB Output is correct
25 Correct 36 ms 13488 KB Output is correct
26 Correct 34 ms 13472 KB Output is correct
27 Correct 38 ms 14596 KB Output is correct
28 Correct 38 ms 14620 KB Output is correct
29 Correct 38 ms 14560 KB Output is correct
30 Correct 39 ms 14576 KB Output is correct
31 Correct 34 ms 12880 KB Output is correct
32 Correct 37 ms 12968 KB Output is correct
33 Correct 40 ms 13512 KB Output is correct
34 Correct 33 ms 13480 KB Output is correct
35 Correct 38 ms 14352 KB Output is correct
36 Correct 41 ms 14380 KB Output is correct
37 Correct 40 ms 14424 KB Output is correct
38 Correct 37 ms 14308 KB Output is correct
39 Correct 43 ms 14536 KB Output is correct
40 Correct 43 ms 14432 KB Output is correct
41 Correct 46 ms 15132 KB Output is correct
42 Correct 41 ms 15208 KB Output is correct
43 Correct 41 ms 15132 KB Output is correct
44 Correct 39 ms 15300 KB Output is correct
45 Correct 39 ms 15176 KB Output is correct
46 Correct 51 ms 15164 KB Output is correct
47 Correct 41 ms 14056 KB Output is correct
48 Correct 37 ms 14120 KB Output is correct
49 Correct 37 ms 14080 KB Output is correct
50 Correct 38 ms 14276 KB Output is correct
51 Correct 36 ms 13084 KB Output is correct
52 Correct 35 ms 13044 KB Output is correct
53 Correct 34 ms 13140 KB Output is correct
54 Correct 35 ms 13008 KB Output is correct
55 Correct 34 ms 13064 KB Output is correct
56 Correct 35 ms 13060 KB Output is correct
57 Correct 34 ms 13228 KB Output is correct
58 Correct 34 ms 13236 KB Output is correct
59 Correct 37 ms 13012 KB Output is correct
60 Correct 36 ms 13100 KB Output is correct