oj.uz

Submission #710458

# Submission time Handle Problem Language Result Execution time Memory
710458 2023-03-15T08:55:32 Z emptypringlescan Stray Cat (JOI20_stray) C++17
15 / 100
 67 ms 21732 KB 
#include <bits/stdc++.h>
using namespace std;
 
 
vector<pair<int,int> > adj[20005],tadj[20005];
int ans[20005];
bool start=false;
int turn=0;
string s="101001";
void dfs(int x, int p, int c){
	int child=0;
	for(auto i:tadj[x]){
		if(i.first==p) continue;
		child++;
	}
	if(child>1){
		start=false;
		turn=0;
		for(auto i:tadj[x]){
			if(i.first==p) continue;
			ans[i.second]=1-c;
			dfs(i.first,x,1-c);
		}
	}
	else if(child==1){
		if(!start){
			start=true;
			turn=1;
			if(c==-1||c==1) turn=0;
			else turn=2;
		}
		for(auto i:tadj[x]){
			if(i.first==p) continue;
			ans[i.second]=s[turn]-'0';
			turn++;
			turn%=6;
			dfs(i.first,x,ans[i.second]);
		}
	}
}
vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V){
	vector<int> ret(M);
	for(int i=0; i<M; i++) ret[i]=-1;
	for(int i=0; i<M; i++){
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}
	if(A>2){
		queue<pair<int,pair<int,int> > > q;
		q.push({0,{0,-1}});
		int v[N];
		memset(v,0,sizeof(v));
		while(!q.empty()){
			int a=q.front().first,b=q.front().second.first,c=q.front().second.second;
			q.pop();
			if(v[b]) continue;
			v[b]=1;
			for(auto i:adj[b]){
				if(ret[i.second]==-1) ret[i.second]=a%3;
				if(!v[i.first]) q.push({a+1,{i.first,0}});
			}
		}
		return ret;
	}
	else{
		for(int i=0; i<M; i++){
			tadj[U[i]].push_back({V[i],i});
			tadj[V[i]].push_back({U[i],i});
		}
	}
	dfs(0,-1,1);
	for(int i=0; i<M; i++) ret[i]=ans[i];
	return ret;
}


#include <bits/stdc++.h>
using namespace std;

bool start=true,confuse=false;
int mode=0;
void Init(int A, int B){
	start=true;
	confuse=false;
	if(A>2) mode=1;
}
int pre=-1;
string cur="";
bool past=false;
int Move(vector<int> y){
	if(mode){
		if(y[0]&&y[1]) return 0;
		else if(y[1]&&y[2]) return 1;
		else if(y[0]&&y[2]) return 2;
		else if(y[0]) return 0;
		else if(y[1]) return 1;
		else if(y[2]) return 2;
		else{
			assert(false);
			return -1;
			
		}
	}
	if(!start&&!confuse){
		if(y[0]+y[1]==1){
			if(y[0]) return pre=0;
			else return pre=1;
		}
		else if(y[0]+y[1]==0){
			assert(false);
			return -1;
		}
		//assert(y[1-pre]==1);
		return pre=1-pre;
	}
	if(start){
		start=false;
		if(y[0]+y[1]==2){
			confuse=true;
			if(y[0]==2){
				cur+="00";
				return pre=0;
			}
			else if(y[1]==2){
				cur+="11";
				return pre=1;
			}
			else{
				cur+="01";
				return pre=1;
			}
		}
		else{
			if(y[0]==1) return pre=0;
			else if(y[1]==1) return pre=1;
			else{
				assert(false);
				return -1;
			}
		}
	}
	if(confuse){
		if(y[0]+y[1]>1){
			if(y[0]==0||y[1]==0){
				confuse=false;
				return -1;
			}
			return pre=1-pre;
		}
		else if(y[0]+y[1]==0){
			confuse=false;
			past=true;
			return -1;
		}
		else{
			if(cur.length()==4){
				if(y[0]) cur+="0";
				else cur+="1";
				if(cur=="10100"||cur=="01001"||cur=="10011"||cur=="00110"||cur=="01101"||cur=="11010"){
					cur="";
					confuse=false;
					return -1;
				}
				else{
					cur="";
					confuse=false;
					if(y[0]) return pre=0;
					else return pre=1;
				}
			}
			if(y[0]){
				cur+="0";
				return pre=0;
			}
			else{
				cur+="1";
				return pre=1;
			}
		}
	}
	return 0;
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:54:51: warning: unused variable 'c' [-Wunused-variable]
   54 |    int a=q.front().first,b=q.front().second.first,c=q.front().second.second;
      |                                                   ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15892 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 31 ms 15560 KB Output is correct
4 Correct 49 ms 16864 KB Output is correct
5 Correct 47 ms 16924 KB Output is correct
6 Correct 34 ms 15712 KB Output is correct
7 Correct 34 ms 15724 KB Output is correct
8 Correct 41 ms 16388 KB Output is correct
9 Correct 43 ms 16316 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 15892 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 31 ms 15560 KB Output is correct
4 Correct 49 ms 16864 KB Output is correct
5 Correct 47 ms 16924 KB Output is correct
6 Correct 34 ms 15712 KB Output is correct
7 Correct 34 ms 15724 KB Output is correct
8 Correct 41 ms 16388 KB Output is correct
9 Correct 43 ms 16316 KB Output is correct
10 Correct 34 ms 13876 KB Output is correct
11 Correct 33 ms 13816 KB Output is correct
12 Correct 36 ms 13756 KB Output is correct
13 Correct 32 ms 13752 KB Output is correct
14 Correct 34 ms 14048 KB Output is correct
15 Correct 35 ms 14416 KB Output is correct
16 Correct 41 ms 16492 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13492 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 31 ms 13108 KB Output is correct
4 Correct 48 ms 14692 KB Output is correct
5 Correct 45 ms 14736 KB Output is correct
6 Correct 33 ms 13492 KB Output is correct
7 Correct 34 ms 13492 KB Output is correct
8 Correct 40 ms 14040 KB Output is correct
9 Correct 39 ms 14016 KB Output is correct
10 Correct 44 ms 13744 KB Output is correct
11 Correct 37 ms 13888 KB Output is correct
12 Correct 38 ms 13776 KB Output is correct
13 Correct 37 ms 13864 KB Output is correct
14 Correct 42 ms 14164 KB Output is correct
15 Correct 39 ms 14076 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 13492 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 31 ms 13108 KB Output is correct
4 Correct 48 ms 14692 KB Output is correct
5 Correct 45 ms 14736 KB Output is correct
6 Correct 33 ms 13492 KB Output is correct
7 Correct 34 ms 13492 KB Output is correct
8 Correct 40 ms 14040 KB Output is correct
9 Correct 39 ms 14016 KB Output is correct
10 Correct 44 ms 13744 KB Output is correct
11 Correct 37 ms 13888 KB Output is correct
12 Correct 38 ms 13776 KB Output is correct
13 Correct 37 ms 13864 KB Output is correct
14 Correct 42 ms 14164 KB Output is correct
15 Correct 39 ms 14076 KB Output is correct
16 Correct 34 ms 11920 KB Output is correct
17 Correct 28 ms 12036 KB Output is correct
18 Correct 30 ms 11888 KB Output is correct
19 Correct 31 ms 11876 KB Output is correct
20 Correct 34 ms 12460 KB Output is correct
21 Correct 35 ms 12272 KB Output is correct
22 Correct 38 ms 14404 KB Output is correct
23 Correct 31 ms 12108 KB Output is correct
24 Correct 31 ms 11972 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1804 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1796 KB Output is correct
4 Correct 2 ms 1804 KB Output is correct
5 Correct 2 ms 1796 KB Output is correct
6 Correct 2 ms 1804 KB Output is correct
7 Correct 2 ms 1796 KB Output is correct
8 Correct 2 ms 1804 KB Output is correct
9 Correct 3 ms 1796 KB Output is correct
10 Correct 2 ms 1796 KB Output is correct
11 Correct 2 ms 1800 KB Output is correct
12 Correct 2 ms 1796 KB Output is correct
13 Correct 2 ms 1796 KB Output is correct
14 Correct 2 ms 1796 KB Output is correct
15 Correct 2 ms 1792 KB Output is correct
16 Correct 2 ms 1808 KB Output is correct
17 Correct 2 ms 1804 KB Output is correct
18 Correct 2 ms 1796 KB Output is correct
19 Correct 2 ms 1804 KB Output is correct
20 Correct 2 ms 1808 KB Output is correct
21 Correct 2 ms 1796 KB Output is correct
22 Correct 2 ms 1796 KB Output is correct
23 Correct 2 ms 1796 KB Output is correct
24 Correct 3 ms 1796 KB Output is correct
25 Runtime error 2 ms 2180 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12372 KB Output is correct
2 Correct 36 ms 13436 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 27 ms 12388 KB Output is correct
5 Correct 45 ms 14672 KB Output is correct
6 Correct 44 ms 14708 KB Output is correct
7 Correct 35 ms 13776 KB Output is correct
8 Correct 35 ms 13956 KB Output is correct
9 Correct 45 ms 14500 KB Output is correct
10 Correct 67 ms 14568 KB Output is correct
11 Correct 41 ms 14656 KB Output is correct
12 Correct 42 ms 14716 KB Output is correct
13 Correct 39 ms 14748 KB Output is correct
14 Correct 40 ms 14584 KB Output is correct
15 Correct 41 ms 14696 KB Output is correct
16 Correct 42 ms 14628 KB Output is correct
17 Correct 45 ms 14228 KB Output is correct
18 Correct 45 ms 14336 KB Output is correct
19 Correct 44 ms 14236 KB Output is correct
20 Correct 39 ms 14320 KB Output is correct
21 Correct 41 ms 14176 KB Output is correct
22 Correct 56 ms 14244 KB Output is correct
23 Correct 43 ms 12332 KB Output is correct
24 Correct 35 ms 12408 KB Output is correct
25 Correct 35 ms 12676 KB Output is correct
26 Correct 41 ms 12604 KB Output is correct
27 Correct 38 ms 13548 KB Output is correct
28 Correct 40 ms 13376 KB Output is correct
29 Correct 40 ms 13500 KB Output is correct
30 Correct 45 ms 13516 KB Output is correct
31 Correct 36 ms 12336 KB Output is correct
32 Correct 33 ms 12360 KB Output is correct
33 Correct 36 ms 12772 KB Output is correct
34 Correct 36 ms 12752 KB Output is correct
35 Correct 40 ms 13416 KB Output is correct
36 Runtime error 37 ms 21732 KB Execution killed with signal 6
37 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12440 KB Output is correct
2 Correct 41 ms 13188 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 29 ms 12272 KB Output is correct
5 Correct 45 ms 14732 KB Output is correct
6 Correct 43 ms 14612 KB Output is correct
7 Correct 37 ms 13744 KB Output is correct
8 Correct 34 ms 13788 KB Output is correct
9 Correct 47 ms 14816 KB Output is correct
10 Correct 45 ms 14684 KB Output is correct
11 Correct 44 ms 14620 KB Output is correct
12 Correct 41 ms 14668 KB Output is correct
13 Correct 43 ms 14608 KB Output is correct
14 Correct 42 ms 14704 KB Output is correct
15 Correct 40 ms 14608 KB Output is correct
16 Correct 45 ms 14624 KB Output is correct
17 Correct 39 ms 14264 KB Output is correct
18 Correct 38 ms 14388 KB Output is correct
19 Correct 42 ms 14356 KB Output is correct
20 Correct 39 ms 14336 KB Output is correct
21 Correct 40 ms 14396 KB Output is correct
22 Correct 40 ms 14444 KB Output is correct
23 Correct 38 ms 12376 KB Output is correct
24 Correct 34 ms 12332 KB Output is correct
25 Correct 36 ms 12688 KB Output is correct
26 Correct 37 ms 12780 KB Output is correct
27 Correct 40 ms 13592 KB Output is correct
28 Correct 47 ms 13592 KB Output is correct
29 Correct 41 ms 13456 KB Output is correct
30 Correct 51 ms 13460 KB Output is correct
31 Correct 38 ms 12316 KB Output is correct
32 Correct 35 ms 12288 KB Output is correct
33 Correct 36 ms 12828 KB Output is correct
34 Correct 36 ms 12700 KB Output is correct
35 Correct 39 ms 13360 KB Output is correct
36 Correct 37 ms 13412 KB Output is correct
37 Correct 36 ms 13428 KB Output is correct
38 Correct 48 ms 13292 KB Output is correct
39 Correct 36 ms 13400 KB Output is correct
40 Correct 40 ms 13344 KB Output is correct
41 Correct 52 ms 13932 KB Output is correct
42 Correct 53 ms 13988 KB Output is correct
43 Correct 56 ms 13876 KB Output is correct
44 Correct 52 ms 13936 KB Output is correct
45 Correct 44 ms 14000 KB Output is correct
46 Correct 50 ms 13840 KB Output is correct
47 Correct 45 ms 13184 KB Output is correct
48 Correct 40 ms 13196 KB Output is correct
49 Runtime error 41 ms 21712 KB Execution killed with signal 6
50 Halted 0 ms 0 KB -