oj.uz

Submission #710286

# Submission time Handle Problem Language Result Execution time Memory
710286 2023-03-15T06:40:22 Z emptypringlescan Stray Cat (JOI20_stray) C++14
5 / 100
 72 ms 17028 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{
				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()==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;
			}
		}
	}
	return 0;
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 2.0

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

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14664 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 41 ms 13892 KB Output is correct
4 Correct 52 ms 16260 KB Output is correct
5 Incorrect 40 ms 16276 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14664 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 41 ms 13892 KB Output is correct
4 Correct 52 ms 16260 KB Output is correct
5 Incorrect 40 ms 16276 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 1788 KB Output is correct
2 Correct 1 ms 1544 KB Output is correct
3 Correct 3 ms 1800 KB Output is correct
4 Correct 2 ms 2024 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 1796 KB Output is correct
8 Correct 2 ms 1808 KB Output is correct
9 Correct 2 ms 1800 KB Output is correct
10 Correct 2 ms 1796 KB Output is correct
11 Correct 2 ms 1804 KB Output is correct
12 Correct 3 ms 1796 KB Output is correct
13 Correct 3 ms 1796 KB Output is correct
14 Correct 2 ms 1804 KB Output is correct
15 Correct 2 ms 1800 KB Output is correct
16 Correct 2 ms 1804 KB Output is correct
17 Correct 4 ms 1796 KB Output is correct
18 Correct 2 ms 1796 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 1776 KB Output is correct
23 Correct 2 ms 1796 KB Output is correct
24 Correct 2 ms 1796 KB Output is correct
25 Correct 2 ms 1820 KB Output is correct
26 Correct 2 ms 1796 KB Output is correct
27 Correct 2 ms 1796 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 41 ms 12268 KB Output is correct
2 Correct 48 ms 13448 KB Output is correct
3 Correct 1 ms 1544 KB Output is correct
4 Correct 37 ms 12184 KB Output is correct
5 Correct 55 ms 14660 KB Output is correct
6 Correct 53 ms 14696 KB Output is correct
7 Correct 52 ms 13796 KB Output is correct
8 Correct 44 ms 13820 KB Output is correct
9 Correct 56 ms 14644 KB Output is correct
10 Correct 55 ms 14632 KB Output is correct
11 Correct 53 ms 14728 KB Output is correct
12 Correct 72 ms 14628 KB Output is correct
13 Correct 42 ms 14612 KB Output is correct
14 Correct 43 ms 14616 KB Output is correct
15 Correct 52 ms 14568 KB Output is correct
16 Correct 46 ms 14616 KB Output is correct
17 Correct 40 ms 14360 KB Output is correct
18 Correct 39 ms 14396 KB Output is correct
19 Correct 39 ms 14380 KB Output is correct
20 Correct 43 ms 14420 KB Output is correct
21 Correct 48 ms 14216 KB Output is correct
22 Correct 49 ms 14324 KB Output is correct
23 Correct 41 ms 12352 KB Output is correct
24 Correct 37 ms 12516 KB Output is correct
25 Correct 36 ms 12708 KB Output is correct
26 Correct 39 ms 12744 KB Output is correct
27 Correct 50 ms 13500 KB Output is correct
28 Correct 40 ms 13540 KB Output is correct
29 Correct 40 ms 13588 KB Output is correct
30 Correct 39 ms 13612 KB Output is correct
31 Correct 33 ms 12432 KB Output is correct
32 Correct 39 ms 12340 KB Output is correct
33 Correct 39 ms 12764 KB Output is correct
34 Correct 35 ms 12732 KB Output is correct
35 Correct 37 ms 13516 KB Output is correct
36 Correct 40 ms 13324 KB Output is correct
37 Incorrect 31 ms 12936 KB Wrong Answer [5]
38 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12312 KB Output is correct
2 Correct 41 ms 13468 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 30 ms 12176 KB Output is correct
5 Correct 44 ms 14640 KB Output is correct
6 Correct 42 ms 14600 KB Output is correct
7 Correct 42 ms 13800 KB Output is correct
8 Correct 35 ms 13708 KB Output is correct
9 Correct 48 ms 14604 KB Output is correct
10 Correct 41 ms 14520 KB Output is correct
11 Correct 48 ms 14592 KB Output is correct
12 Correct 48 ms 14596 KB Output is correct
13 Correct 44 ms 14692 KB Output is correct
14 Correct 44 ms 14652 KB Output is correct
15 Incorrect 45 ms 14584 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -