oj.uz

Submission #287054

# Submission time Handle Problem Language Result Execution time Memory
287054 2020-08-31T10:32:37 Z TadijaSebez Stray Cat (JOI20_stray) C++14
100 / 100
 69 ms 19364 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>

namespace {
	const int N=100050;
	int dist[N];
	vector<int> E[N];
	void AddEdge(int u,int v){E[u].pb(v);E[v].pb(u);}
	void BFS(int n,int m){
		queue<int> q;
		q.push(0);dist[0]=1;
		while(q.size()){
			int u=q.front();
			q.pop();
			for(int v:E[u])if(!dist[v]){
				dist[v]=dist[u]+1;
				q.push(v);
			}
		}
	}
	vector<int> Solve(int n,int m,vector<int> u,vector<int> v){
		vector<int> col;
		for(int i=0;i<m;i++){
			int a=u[i],b=v[i];
			if(dist[a]>dist[b])swap(a,b);
			if(dist[a]==dist[b])col.pb((dist[b]+1)%3);
			else col.pb(dist[b]%3);
		}
		return col;
	}
	vector<int> Solve2(int n,int m,vector<int> u,vector<int> v){
		vector<int> col(m);
		/*for(int i=0;i<m;i++){
			int a=u[i],b=v[i];
			if(dist[a]>dist[b])swap(a,b);
			if(dist[a]==dist[b])col.pb((dist[b]+1)%2);
			else col.pb(dist[b]%2);
		}*/
		vector<vector<pii>> E(n);
		for(int i=0;i<m;i++)E[u[i]].pb({v[i],i}),E[v[i]].pb({u[i],i});
		vector<int> patern={0,1,0,0,1,1};
		function<void(int,int,int)> DFS=[&](int u,int p,int c){
			int deg=E[u].size();
			if(p!=-1)deg--;
			if(u){
				if(deg==1)c=(c+1)%6;
				else c=patern[c]^1;
			}
			for(auto e:E[u])if(e.first!=p){
				col[e.second]=patern[c];
				DFS(e.first,u,c);
			}
		};
		DFS(0,-1,0);
		return col;
	}
}  // namespace

vector<int> Mark(int n,int m,int a,int b,vector<int> u,vector<int> v){
	for(int i=0;i<m;i++)AddEdge(u[i],v[i]);
	BFS(n,m);
	if(a>2)return Solve(n,m,u,v);
	else return Solve2(n,m,u,v);
}
#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

namespace {
	int a,b,now,last,turn;
	bool fir,sibaj;
	vector<int> bits,patern={0,1,0,0,1,1};
	bool Check(){
		for(int i=0;i<6;i++){
			bool ok=1;
			for(int j=0;j<5;j++){
				if(bits[j]!=patern[(i+j)%6])
					ok=0;
			}
			if(ok)return 1;
		}
		return 0;
	}
}  // namespace

void Init(int a,int b){
	::a=a;
	::b=b;
	fir=1;
	turn=0;
	last=-1;
	if(a==2){
		now=1;
		sibaj=0;
		bits.clear();
	}
}

int Move(vector<int> y){
	if(a>2){
		int cnt=0;
		for(int i=0;i<3;i++)if(y[i]!=0)cnt++;
		if(cnt<2){
			assert(cnt==1);
			for(int i=0;i<3;i++)if(y[i]!=0)now=i;
		}else{
			assert(cnt==2);
			if(y[0]==0)now=1;
			else if(y[1]==0)now=2;
			else now=0;
		}
		return now;
	}else{
		turn++;
		int deg=y[0]+y[1]+(turn!=1);
		if(sibaj){
			if(y[last^1])return last^=1;
			else return last;
		}else if(deg>2){
			sibaj=1;
			if(turn!=1)y[last]++;
			int col;
			if(y[0]==1)col=0;
			else col=1;
			if(last==col)return -1;
			else return last=col;
		}else if(deg==1){
			sibaj=1;
			if(turn==1)return last=(y[0]?0:1);
			else return -1;
		}else{
			if(turn==1){
				for(int i=0;i<y[0];i++)bits.pb(0);
				for(int i=0;i<y[1];i++)bits.pb(1);
                return last=bits.back();
			}else if(turn<4){
				int col;
				if(y[0])col=0;
				else col=1;
				bits.pb(col);
				return last=col;
			}else if(turn==4){
				int col;
				if(y[0])col=0;
				else col=1;
				bits.pb(col);
				sibaj=1;
				if(Check())return -1;
				else return last=col;
			}
		}
	}
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18116 KB Output is correct
2 Correct 3 ms 5376 KB Output is correct
3 Correct 41 ms 17384 KB Output is correct
4 Correct 67 ms 19160 KB Output is correct
5 Correct 69 ms 19364 KB Output is correct
6 Correct 53 ms 17836 KB Output is correct
7 Correct 52 ms 17968 KB Output is correct
8 Correct 60 ms 18480 KB Output is correct
9 Correct 67 ms 18500 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18116 KB Output is correct
2 Correct 3 ms 5376 KB Output is correct
3 Correct 41 ms 17384 KB Output is correct
4 Correct 67 ms 19160 KB Output is correct
5 Correct 69 ms 19364 KB Output is correct
6 Correct 53 ms 17836 KB Output is correct
7 Correct 52 ms 17968 KB Output is correct
8 Correct 60 ms 18480 KB Output is correct
9 Correct 67 ms 18500 KB Output is correct
10 Correct 47 ms 15780 KB Output is correct
11 Correct 47 ms 16016 KB Output is correct
12 Correct 50 ms 16016 KB Output is correct
13 Correct 49 ms 15884 KB Output is correct
14 Correct 49 ms 15968 KB Output is correct
15 Correct 56 ms 16680 KB Output is correct
16 Correct 61 ms 18796 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15544 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 47 ms 15120 KB Output is correct
4 Correct 63 ms 17012 KB Output is correct
5 Correct 63 ms 17096 KB Output is correct
6 Correct 48 ms 15788 KB Output is correct
7 Correct 48 ms 15912 KB Output is correct
8 Correct 57 ms 16312 KB Output is correct
9 Correct 59 ms 16328 KB Output is correct
10 Correct 52 ms 16056 KB Output is correct
11 Correct 52 ms 16084 KB Output is correct
12 Correct 57 ms 15920 KB Output is correct
13 Correct 54 ms 16188 KB Output is correct
14 Correct 57 ms 16312 KB Output is correct
15 Correct 57 ms 16176 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15544 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 47 ms 15120 KB Output is correct
4 Correct 63 ms 17012 KB Output is correct
5 Correct 63 ms 17096 KB Output is correct
6 Correct 48 ms 15788 KB Output is correct
7 Correct 48 ms 15912 KB Output is correct
8 Correct 57 ms 16312 KB Output is correct
9 Correct 59 ms 16328 KB Output is correct
10 Correct 52 ms 16056 KB Output is correct
11 Correct 52 ms 16084 KB Output is correct
12 Correct 57 ms 15920 KB Output is correct
13 Correct 54 ms 16188 KB Output is correct
14 Correct 57 ms 16312 KB Output is correct
15 Correct 57 ms 16176 KB Output is correct
16 Correct 43 ms 14008 KB Output is correct
17 Correct 43 ms 14040 KB Output is correct
18 Correct 44 ms 14156 KB Output is correct
19 Correct 44 ms 14000 KB Output is correct
20 Correct 52 ms 14676 KB Output is correct
21 Correct 50 ms 14504 KB Output is correct
22 Correct 55 ms 16624 KB Output is correct
23 Correct 45 ms 14000 KB Output is correct
24 Correct 46 ms 14128 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14936 KB Output is correct
2 Correct 57 ms 16228 KB Output is correct
3 Correct 2 ms 5376 KB Output is correct
4 Correct 40 ms 14612 KB Output is correct
5 Correct 63 ms 17936 KB Output is correct
6 Correct 68 ms 17932 KB Output is correct
7 Correct 55 ms 17172 KB Output is correct
8 Correct 55 ms 17184 KB Output is correct
9 Correct 67 ms 18204 KB Output is correct
10 Correct 64 ms 18080 KB Output is correct
11 Correct 64 ms 17996 KB Output is correct
12 Correct 65 ms 17944 KB Output is correct
13 Correct 65 ms 17936 KB Output is correct
14 Correct 64 ms 17956 KB Output is correct
15 Correct 69 ms 17944 KB Output is correct
16 Correct 68 ms 18152 KB Output is correct
17 Correct 61 ms 17932 KB Output is correct
18 Correct 61 ms 17676 KB Output is correct
19 Correct 59 ms 17688 KB Output is correct
20 Correct 60 ms 17668 KB Output is correct
21 Correct 61 ms 17756 KB Output is correct
22 Correct 59 ms 17492 KB Output is correct
23 Correct 50 ms 14688 KB Output is correct
24 Correct 51 ms 14688 KB Output is correct
25 Correct 51 ms 15196 KB Output is correct
26 Correct 51 ms 15212 KB Output is correct
27 Correct 61 ms 16472 KB Output is correct
28 Correct 57 ms 16352 KB Output is correct
29 Correct 58 ms 16592 KB Output is correct
30 Correct 59 ms 16480 KB Output is correct
31 Correct 50 ms 14676 KB Output is correct
32 Correct 49 ms 14548 KB Output is correct
33 Correct 51 ms 15424 KB Output is correct
34 Correct 50 ms 15304 KB Output is correct
35 Correct 56 ms 16332 KB Output is correct
36 Correct 55 ms 16076 KB Output is correct
37 Correct 55 ms 16076 KB Output is correct
38 Correct 62 ms 16212 KB Output is correct
39 Correct 55 ms 16084 KB Output is correct
40 Correct 56 ms 16460 KB Output is correct
41 Correct 59 ms 17012 KB Output is correct
42 Correct 59 ms 16868 KB Output is correct
43 Correct 61 ms 16852 KB Output is correct
44 Correct 63 ms 16868 KB Output is correct
45 Correct 60 ms 16972 KB Output is correct
46 Correct 60 ms 16992 KB Output is correct
47 Correct 53 ms 16056 KB Output is correct
48 Correct 55 ms 16176 KB Output is correct
49 Correct 54 ms 16056 KB Output is correct
50 Correct 55 ms 16140 KB Output is correct
51 Correct 49 ms 14728 KB Output is correct
52 Correct 50 ms 14668 KB Output is correct
53 Correct 49 ms 14820 KB Output is correct
54 Correct 49 ms 14808 KB Output is correct
55 Correct 51 ms 15092 KB Output is correct
56 Correct 52 ms 15212 KB Output is correct
57 Correct 49 ms 14668 KB Output is correct
58 Correct 50 ms 14844 KB Output is correct
59 Correct 50 ms 14864 KB Output is correct
60 Correct 50 ms 14800 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14688 KB Output is correct
2 Correct 54 ms 15968 KB Output is correct
3 Correct 2 ms 5376 KB Output is correct
4 Correct 44 ms 14668 KB Output is correct
5 Correct 64 ms 18068 KB Output is correct
6 Correct 64 ms 17868 KB Output is correct
7 Correct 51 ms 17044 KB Output is correct
8 Correct 55 ms 17048 KB Output is correct
9 Correct 62 ms 17960 KB Output is correct
10 Correct 63 ms 18060 KB Output is correct
11 Correct 66 ms 18088 KB Output is correct
12 Correct 64 ms 18136 KB Output is correct
13 Correct 64 ms 18200 KB Output is correct
14 Correct 68 ms 17868 KB Output is correct
15 Correct 64 ms 18188 KB Output is correct
16 Correct 64 ms 17908 KB Output is correct
17 Correct 60 ms 17612 KB Output is correct
18 Correct 60 ms 17692 KB Output is correct
19 Correct 59 ms 17612 KB Output is correct
20 Correct 59 ms 17688 KB Output is correct
21 Correct 59 ms 17620 KB Output is correct
22 Correct 61 ms 17864 KB Output is correct
23 Correct 48 ms 14692 KB Output is correct
24 Correct 50 ms 14928 KB Output is correct
25 Correct 50 ms 15184 KB Output is correct
26 Correct 49 ms 15216 KB Output is correct
27 Correct 57 ms 16204 KB Output is correct
28 Correct 59 ms 16120 KB Output is correct
29 Correct 61 ms 16468 KB Output is correct
30 Correct 57 ms 16468 KB Output is correct
31 Correct 49 ms 14700 KB Output is correct
32 Correct 49 ms 14696 KB Output is correct
33 Correct 51 ms 15440 KB Output is correct
34 Correct 51 ms 15188 KB Output is correct
35 Correct 56 ms 16332 KB Output is correct
36 Correct 57 ms 16332 KB Output is correct
37 Correct 56 ms 16084 KB Output is correct
38 Correct 56 ms 16340 KB Output is correct
39 Correct 60 ms 16212 KB Output is correct
40 Correct 56 ms 16340 KB Output is correct
41 Correct 60 ms 17252 KB Output is correct
42 Correct 59 ms 16856 KB Output is correct
43 Correct 61 ms 16984 KB Output is correct
44 Correct 60 ms 16876 KB Output is correct
45 Correct 61 ms 17000 KB Output is correct
46 Correct 61 ms 16852 KB Output is correct
47 Correct 54 ms 15992 KB Output is correct
48 Correct 55 ms 16064 KB Output is correct
49 Correct 53 ms 15828 KB Output is correct
50 Correct 54 ms 15956 KB Output is correct
51 Correct 50 ms 14704 KB Output is correct
52 Correct 51 ms 14820 KB Output is correct
53 Correct 50 ms 14808 KB Output is correct
54 Correct 50 ms 14804 KB Output is correct
55 Correct 50 ms 14676 KB Output is correct
56 Correct 50 ms 14912 KB Output is correct
57 Correct 50 ms 14676 KB Output is correct
58 Correct 50 ms 14848 KB Output is correct
59 Correct 50 ms 14984 KB Output is correct
60 Correct 49 ms 14856 KB Output is correct