oj.uz

Submission #710284

# Submission time Handle Problem Language Result Execution time Memory
710284 2023-03-15T06:39:21 Z emptypringlescan Stray Cat (JOI20_stray) C++17
5 / 100
 63 ms 21648 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;
			}
			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 47 ms 17048 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

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

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14640 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 39 ms 14016 KB Output is correct
4 Correct 46 ms 16304 KB Output is correct
5 Incorrect 51 ms 16236 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 14640 KB Output is correct
2 Correct 2 ms 1536 KB Output is correct
3 Correct 39 ms 14016 KB Output is correct
4 Correct 46 ms 16304 KB Output is correct
5 Incorrect 51 ms 16236 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 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 3 ms 1796 KB Output is correct
5 Correct 2 ms 1804 KB Output is correct
6 Correct 2 ms 1932 KB Output is correct
7 Correct 2 ms 1804 KB Output is correct
8 Correct 2 ms 1804 KB Output is correct
9 Correct 2 ms 1804 KB Output is correct
10 Correct 2 ms 1796 KB Output is correct
11 Correct 3 ms 1804 KB Output is correct
12 Correct 3 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 1796 KB Output is correct
16 Correct 2 ms 1796 KB Output is correct
17 Correct 2 ms 1804 KB Output is correct
18 Correct 2 ms 1800 KB Output is correct
19 Correct 2 ms 1796 KB Output is correct
20 Correct 2 ms 1804 KB Output is correct
21 Correct 2 ms 1800 KB Output is correct
22 Correct 2 ms 1796 KB Output is correct
23 Correct 2 ms 1796 KB Output is correct
24 Correct 2 ms 1804 KB Output is correct
25 Correct 2 ms 1800 KB Output is correct
26 Correct 2 ms 1804 KB Output is correct
27 Correct 2 ms 1804 KB Output is correct
28 Correct 2 ms 1808 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12416 KB Output is correct
2 Correct 39 ms 13428 KB Output is correct
3 Correct 1 ms 1544 KB Output is correct
4 Correct 36 ms 12264 KB Output is correct
5 Correct 56 ms 14496 KB Output is correct
6 Correct 41 ms 14612 KB Output is correct
7 Correct 36 ms 13816 KB Output is correct
8 Correct 44 ms 13720 KB Output is correct
9 Correct 63 ms 14612 KB Output is correct
10 Correct 47 ms 14548 KB Output is correct
11 Correct 44 ms 14544 KB Output is correct
12 Correct 45 ms 14528 KB Output is correct
13 Correct 47 ms 14488 KB Output is correct
14 Correct 48 ms 14668 KB Output is correct
15 Correct 48 ms 14688 KB Output is correct
16 Correct 44 ms 14644 KB Output is correct
17 Correct 41 ms 14272 KB Output is correct
18 Correct 41 ms 14440 KB Output is correct
19 Correct 50 ms 14396 KB Output is correct
20 Correct 43 ms 14248 KB Output is correct
21 Correct 39 ms 14316 KB Output is correct
22 Correct 40 ms 14332 KB Output is correct
23 Correct 35 ms 12444 KB Output is correct
24 Correct 37 ms 12428 KB Output is correct
25 Correct 35 ms 12652 KB Output is correct
26 Correct 34 ms 12596 KB Output is correct
27 Correct 39 ms 13584 KB Output is correct
28 Correct 45 ms 13460 KB Output is correct
29 Correct 40 ms 13516 KB Output is correct
30 Correct 44 ms 13492 KB Output is correct
31 Correct 32 ms 12340 KB Output is correct
32 Correct 34 ms 12392 KB Output is correct
33 Correct 36 ms 12704 KB Output is correct
34 Correct 39 ms 12708 KB Output is correct
35 Correct 45 ms 13384 KB Output is correct
36 Correct 38 ms 13408 KB Output is correct
37 Runtime error 38 ms 21648 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 35 ms 12408 KB Output is correct
2 Correct 34 ms 13268 KB Output is correct
3 Correct 1 ms 1544 KB Output is correct
4 Correct 29 ms 12280 KB Output is correct
5 Correct 45 ms 14612 KB Output is correct
6 Correct 47 ms 14648 KB Output is correct
7 Correct 39 ms 13800 KB Output is correct
8 Correct 38 ms 13784 KB Output is correct
9 Correct 46 ms 14536 KB Output is correct
10 Correct 44 ms 14632 KB Output is correct
11 Correct 43 ms 14660 KB Output is correct
12 Correct 47 ms 14544 KB Output is correct
13 Correct 43 ms 14580 KB Output is correct
14 Correct 44 ms 14644 KB Output is correct
15 Incorrect 43 ms 14560 KB Wrong Answer [6]
16 Halted 0 ms 0 KB -