oj.uz

Submission #710283

# Submission time Handle Problem Language Result Execution time Memory
710283 2023-03-15T06:38:19 Z emptypringlescan Stray Cat (JOI20_stray) C++17
5 / 100
 47 ms 21660 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=0;
		}
		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++){
		adj[U[i]].push_back({V[i],i});
		adj[V[i]].push_back({U[i],i});
	}
	if(A>2){
		priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > > pq;
		pq.push({0,{0,-1}});
		int v[N],tree[M];
		memset(tree,0,sizeof(tree));
		memset(v,0,sizeof(v));
		while(!pq.empty()){
			int a=pq.top().first,b=pq.top().second.first,c=pq.top().second.second;
			pq.pop();
			if(v[b]) continue;
			v[b]=1;
			if(c!=-1){
				tree[c]=1;
			}
			for(auto i:adj[b]){
				if(!v[i.first]) pq.push({a+1,{i.first,i.second}});
			}
		}
		for(int i=0; i<M; i++){
			if(!tree[i]) ret[i]=ans[i]=2;
			else{
				tadj[U[i]].push_back({V[i],i});
				tadj[V[i]].push_back({U[i],i});
			}
		}
	}
	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;
void Init(int A, int B){
	start=true;
	confuse=false;
}
int pre=-1;
string cur="";
int Move(vector<int> y){
	if(!start&&!confuse){
		if(y[0]+y[1]==1){
			if(y[0]) return pre=0;
			else return pre=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]){
				cur+="0";
				return pre=0;
			}
			else{
				cur+="1";
				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;
			}
			//assert(y[1-pre]==1);
			return pre=1-pre;
		}
		else if(y[0]+y[1]==0){
			confuse=false;
			return -1;
		}
		else{
			if(cur.length()==6){
				if(cur=="101001"||cur=="010011"||cur=="100110"||cur=="001101"||cur=="011010"||cur=="110100"){
					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;
			}
		}
	}
	//assert(false);
	return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 17072 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 17072 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14716 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 37 ms 13928 KB Output is correct
4 Correct 46 ms 16140 KB Output is correct
5 Incorrect 41 ms 16252 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14716 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 37 ms 13928 KB Output is correct
4 Correct 46 ms 16140 KB Output is correct
5 Incorrect 41 ms 16252 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1808 KB Output is correct
2 Correct 1 ms 1540 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 1796 KB Output is correct
6 Correct 2 ms 1792 KB Output is correct
7 Correct 2 ms 1800 KB Output is correct
8 Correct 2 ms 1804 KB Output is correct
9 Correct 2 ms 1888 KB Output is correct
10 Correct 2 ms 1796 KB Output is correct
11 Correct 2 ms 1804 KB Output is correct
12 Correct 2 ms 1800 KB Output is correct
13 Correct 2 ms 1804 KB Output is correct
14 Correct 2 ms 1796 KB Output is correct
15 Correct 2 ms 1804 KB Output is correct
16 Correct 2 ms 1804 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 1796 KB Output is correct
20 Correct 2 ms 1796 KB Output is correct
21 Correct 2 ms 1804 KB Output is correct
22 Correct 2 ms 1804 KB Output is correct
23 Correct 2 ms 1800 KB Output is correct
24 Correct 2 ms 1796 KB Output is correct
25 Correct 2 ms 1804 KB Output is correct
26 Correct 2 ms 1796 KB Output is correct
27 Correct 2 ms 1804 KB Output is correct
28 Correct 2 ms 1804 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12316 KB Output is correct
2 Correct 37 ms 13412 KB Output is correct
3 Correct 1 ms 1544 KB Output is correct
4 Correct 30 ms 12204 KB Output is correct
5 Correct 42 ms 14616 KB Output is correct
6 Correct 45 ms 14676 KB Output is correct
7 Correct 36 ms 13600 KB Output is correct
8 Correct 35 ms 13788 KB Output is correct
9 Correct 41 ms 14644 KB Output is correct
10 Correct 41 ms 14624 KB Output is correct
11 Correct 41 ms 14676 KB Output is correct
12 Correct 40 ms 14632 KB Output is correct
13 Correct 41 ms 14712 KB Output is correct
14 Correct 40 ms 14548 KB Output is correct
15 Correct 40 ms 14656 KB Output is correct
16 Correct 42 ms 14496 KB Output is correct
17 Correct 38 ms 14456 KB Output is correct
18 Correct 41 ms 14288 KB Output is correct
19 Correct 47 ms 14224 KB Output is correct
20 Correct 37 ms 14288 KB Output is correct
21 Correct 39 ms 14436 KB Output is correct
22 Correct 39 ms 14336 KB Output is correct
23 Correct 33 ms 12368 KB Output is correct
24 Correct 33 ms 12300 KB Output is correct
25 Correct 34 ms 12752 KB Output is correct
26 Correct 35 ms 12676 KB Output is correct
27 Correct 40 ms 13552 KB Output is correct
28 Correct 41 ms 13544 KB Output is correct
29 Correct 39 ms 13500 KB Output is correct
30 Correct 43 ms 13564 KB Output is correct
31 Correct 36 ms 12348 KB Output is correct
32 Correct 32 ms 12404 KB Output is correct
33 Correct 35 ms 12828 KB Output is correct
34 Correct 32 ms 12824 KB Output is correct
35 Correct 37 ms 13408 KB Output is correct
36 Correct 38 ms 13424 KB Output is correct
37 Runtime error 37 ms 21660 KB Execution killed with signal 6
38 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12340 KB Output is correct
2 Correct 35 ms 13264 KB Output is correct
3 Correct 1 ms 1544 KB Output is correct
4 Correct 31 ms 12208 KB Output is correct
5 Correct 42 ms 14780 KB Output is correct
6 Correct 43 ms 14668 KB Output is correct
7 Correct 36 ms 13744 KB Output is correct
8 Correct 35 ms 13720 KB Output is correct
9 Correct 43 ms 14628 KB Output is correct
10 Correct 46 ms 14720 KB Output is correct
11 Correct 42 ms 14616 KB Output is correct
12 Correct 40 ms 14748 KB Output is correct
13 Correct 42 ms 14656 KB Output is correct
14 Correct 41 ms 14700 KB Output is correct
15 Incorrect 41 ms 14660 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -