oj.uz

Submission #710454

# Submission time Handle Problem Language Result Execution time Memory
710454 2023-03-15T08:54:14 Z emptypringlescan Stray Cat (JOI20_stray) C++17
15 / 100
 71 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;
			past=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;
			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 36 ms 15936 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 28 ms 15396 KB Output is correct
4 Correct 53 ms 16956 KB Output is correct
5 Correct 45 ms 16904 KB Output is correct
6 Correct 34 ms 15700 KB Output is correct
7 Correct 36 ms 15680 KB Output is correct
8 Correct 45 ms 16476 KB Output is correct
9 Correct 54 ms 16280 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15936 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 28 ms 15396 KB Output is correct
4 Correct 53 ms 16956 KB Output is correct
5 Correct 45 ms 16904 KB Output is correct
6 Correct 34 ms 15700 KB Output is correct
7 Correct 36 ms 15680 KB Output is correct
8 Correct 45 ms 16476 KB Output is correct
9 Correct 54 ms 16280 KB Output is correct
10 Correct 33 ms 13920 KB Output is correct
11 Correct 33 ms 13936 KB Output is correct
12 Correct 34 ms 13756 KB Output is correct
13 Correct 33 ms 13704 KB Output is correct
14 Correct 38 ms 13972 KB Output is correct
15 Correct 54 ms 14296 KB Output is correct
16 Correct 43 ms 16512 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13404 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 36 ms 13244 KB Output is correct
4 Correct 55 ms 14712 KB Output is correct
5 Correct 41 ms 14768 KB Output is correct
6 Correct 32 ms 13524 KB Output is correct
7 Correct 36 ms 13508 KB Output is correct
8 Correct 44 ms 13984 KB Output is correct
9 Correct 44 ms 14096 KB Output is correct
10 Correct 39 ms 13720 KB Output is correct
11 Correct 37 ms 13776 KB Output is correct
12 Correct 38 ms 13900 KB Output is correct
13 Correct 45 ms 13820 KB Output is correct
14 Correct 44 ms 14188 KB Output is correct
15 Correct 39 ms 14084 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13404 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 36 ms 13244 KB Output is correct
4 Correct 55 ms 14712 KB Output is correct
5 Correct 41 ms 14768 KB Output is correct
6 Correct 32 ms 13524 KB Output is correct
7 Correct 36 ms 13508 KB Output is correct
8 Correct 44 ms 13984 KB Output is correct
9 Correct 44 ms 14096 KB Output is correct
10 Correct 39 ms 13720 KB Output is correct
11 Correct 37 ms 13776 KB Output is correct
12 Correct 38 ms 13900 KB Output is correct
13 Correct 45 ms 13820 KB Output is correct
14 Correct 44 ms 14188 KB Output is correct
15 Correct 39 ms 14084 KB Output is correct
16 Correct 32 ms 12004 KB Output is correct
17 Correct 34 ms 11992 KB Output is correct
18 Correct 34 ms 11864 KB Output is correct
19 Correct 34 ms 11856 KB Output is correct
20 Correct 41 ms 12516 KB Output is correct
21 Correct 32 ms 12280 KB Output is correct
22 Correct 38 ms 14344 KB Output is correct
23 Correct 37 ms 11928 KB Output is correct
24 Correct 34 ms 11960 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1796 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 2 ms 1796 KB Output is correct
4 Correct 2 ms 1796 KB Output is correct
5 Correct 2 ms 1804 KB Output is correct
6 Correct 2 ms 1796 KB Output is correct
7 Correct 2 ms 1804 KB Output is correct
8 Correct 2 ms 1796 KB Output is correct
9 Correct 2 ms 1804 KB Output is correct
10 Correct 2 ms 1804 KB Output is correct
11 Correct 3 ms 1796 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 1816 KB Output is correct
15 Correct 2 ms 1796 KB Output is correct
16 Correct 2 ms 1796 KB Output is correct
17 Correct 2 ms 1796 KB Output is correct
18 Correct 3 ms 1804 KB Output is correct
19 Correct 3 ms 1796 KB Output is correct
20 Correct 2 ms 1796 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 1804 KB Output is correct
24 Correct 2 ms 1804 KB Output is correct
25 Runtime error 2 ms 2188 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 35 ms 12364 KB Output is correct
2 Correct 44 ms 13384 KB Output is correct
3 Correct 1 ms 1532 KB Output is correct
4 Correct 35 ms 12212 KB Output is correct
5 Correct 51 ms 14568 KB Output is correct
6 Correct 46 ms 14540 KB Output is correct
7 Correct 35 ms 13816 KB Output is correct
8 Correct 38 ms 13808 KB Output is correct
9 Correct 47 ms 14672 KB Output is correct
10 Correct 47 ms 14704 KB Output is correct
11 Correct 50 ms 14600 KB Output is correct
12 Correct 45 ms 14656 KB Output is correct
13 Correct 43 ms 14696 KB Output is correct
14 Correct 40 ms 14648 KB Output is correct
15 Correct 41 ms 14508 KB Output is correct
16 Correct 41 ms 14568 KB Output is correct
17 Correct 40 ms 14388 KB Output is correct
18 Correct 38 ms 14324 KB Output is correct
19 Correct 44 ms 14324 KB Output is correct
20 Correct 38 ms 14428 KB Output is correct
21 Correct 41 ms 14364 KB Output is correct
22 Correct 41 ms 14364 KB Output is correct
23 Correct 33 ms 12372 KB Output is correct
24 Correct 36 ms 12316 KB Output is correct
25 Correct 37 ms 12724 KB Output is correct
26 Correct 41 ms 12676 KB Output is correct
27 Correct 43 ms 13596 KB Output is correct
28 Correct 40 ms 13448 KB Output is correct
29 Correct 44 ms 13464 KB Output is correct
30 Correct 42 ms 13480 KB Output is correct
31 Correct 37 ms 12396 KB Output is correct
32 Correct 39 ms 12424 KB Output is correct
33 Correct 33 ms 12788 KB Output is correct
34 Correct 37 ms 12604 KB Output is correct
35 Correct 44 ms 13508 KB Output is correct
36 Runtime error 39 ms 21628 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 43 ms 12404 KB Output is correct
2 Correct 37 ms 13284 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 32 ms 12224 KB Output is correct
5 Correct 46 ms 14684 KB Output is correct
6 Correct 50 ms 14500 KB Output is correct
7 Correct 59 ms 13708 KB Output is correct
8 Correct 43 ms 13872 KB Output is correct
9 Correct 44 ms 14700 KB Output is correct
10 Correct 43 ms 14724 KB Output is correct
11 Correct 43 ms 14736 KB Output is correct
12 Correct 50 ms 14640 KB Output is correct
13 Correct 54 ms 14580 KB Output is correct
14 Correct 57 ms 14620 KB Output is correct
15 Correct 42 ms 14548 KB Output is correct
16 Correct 46 ms 14644 KB Output is correct
17 Correct 44 ms 14308 KB Output is correct
18 Correct 44 ms 14280 KB Output is correct
19 Correct 59 ms 14272 KB Output is correct
20 Correct 39 ms 14268 KB Output is correct
21 Correct 38 ms 14304 KB Output is correct
22 Correct 44 ms 14412 KB Output is correct
23 Correct 48 ms 12196 KB Output is correct
24 Correct 43 ms 12356 KB Output is correct
25 Correct 37 ms 12748 KB Output is correct
26 Correct 48 ms 12596 KB Output is correct
27 Correct 44 ms 13504 KB Output is correct
28 Correct 44 ms 13380 KB Output is correct
29 Correct 40 ms 13556 KB Output is correct
30 Correct 43 ms 13472 KB Output is correct
31 Correct 52 ms 12272 KB Output is correct
32 Correct 46 ms 12316 KB Output is correct
33 Correct 48 ms 12772 KB Output is correct
34 Correct 47 ms 12644 KB Output is correct
35 Correct 40 ms 13408 KB Output is correct
36 Correct 40 ms 13352 KB Output is correct
37 Correct 54 ms 13416 KB Output is correct
38 Correct 46 ms 13304 KB Output is correct
39 Correct 46 ms 13392 KB Output is correct
40 Correct 41 ms 13396 KB Output is correct
41 Correct 43 ms 13972 KB Output is correct
42 Correct 52 ms 13872 KB Output is correct
43 Correct 51 ms 13832 KB Output is correct
44 Correct 51 ms 13944 KB Output is correct
45 Correct 71 ms 13812 KB Output is correct
46 Correct 69 ms 13824 KB Output is correct
47 Correct 59 ms 13148 KB Output is correct
48 Correct 64 ms 13076 KB Output is correct
49 Runtime error 66 ms 21732 KB Execution killed with signal 6
50 Halted 0 ms 0 KB -