oj.uz

Submission #710403

# Submission time Handle Problem Language Result Execution time Memory
710403 2023-03-15T08:19:36 Z emptypringlescan Stray Cat (JOI20_stray) C++14
15 / 100
 48 ms 16884 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 e){
	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,i.second);
		}
	}
	else if(child==1){
		if(!start){
			start=true;
			turn=1;
			if(e!=-1) ans[e]=s[0]-'0';
			else 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],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,-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="";
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) 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+="10";
				return pre=0;
			}
		}
		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 48 ms 15836 KB Output is correct
2 Correct 2 ms 1540 KB Output is correct
3 Correct 39 ms 15328 KB Output is correct
4 Correct 45 ms 16872 KB Output is correct
5 Correct 45 ms 16884 KB Output is correct
6 Correct 36 ms 15580 KB Output is correct
7 Correct 37 ms 15728 KB Output is correct
8 Correct 44 ms 16356 KB Output is correct
9 Correct 47 ms 16364 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15836 KB Output is correct
2 Correct 2 ms 1540 KB Output is correct
3 Correct 39 ms 15328 KB Output is correct
4 Correct 45 ms 16872 KB Output is correct
5 Correct 45 ms 16884 KB Output is correct
6 Correct 36 ms 15580 KB Output is correct
7 Correct 37 ms 15728 KB Output is correct
8 Correct 44 ms 16356 KB Output is correct
9 Correct 47 ms 16364 KB Output is correct
10 Correct 33 ms 13716 KB Output is correct
11 Correct 36 ms 13784 KB Output is correct
12 Correct 34 ms 13712 KB Output is correct
13 Correct 34 ms 13712 KB Output is correct
14 Correct 34 ms 14000 KB Output is correct
15 Correct 37 ms 14368 KB Output is correct
16 Correct 43 ms 16472 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13492 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 28 ms 13272 KB Output is correct
4 Correct 43 ms 14716 KB Output is correct
5 Correct 46 ms 14732 KB Output is correct
6 Correct 33 ms 13544 KB Output is correct
7 Correct 33 ms 13552 KB Output is correct
8 Correct 41 ms 14064 KB Output is correct
9 Correct 38 ms 14052 KB Output is correct
10 Correct 37 ms 13896 KB Output is correct
11 Correct 39 ms 13828 KB Output is correct
12 Correct 43 ms 13804 KB Output is correct
13 Correct 38 ms 13828 KB Output is correct
14 Correct 41 ms 14160 KB Output is correct
15 Correct 41 ms 14196 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13492 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 28 ms 13272 KB Output is correct
4 Correct 43 ms 14716 KB Output is correct
5 Correct 46 ms 14732 KB Output is correct
6 Correct 33 ms 13544 KB Output is correct
7 Correct 33 ms 13552 KB Output is correct
8 Correct 41 ms 14064 KB Output is correct
9 Correct 38 ms 14052 KB Output is correct
10 Correct 37 ms 13896 KB Output is correct
11 Correct 39 ms 13828 KB Output is correct
12 Correct 43 ms 13804 KB Output is correct
13 Correct 38 ms 13828 KB Output is correct
14 Correct 41 ms 14160 KB Output is correct
15 Correct 41 ms 14196 KB Output is correct
16 Correct 31 ms 12104 KB Output is correct
17 Correct 31 ms 12116 KB Output is correct
18 Correct 32 ms 11860 KB Output is correct
19 Correct 32 ms 11876 KB Output is correct
20 Correct 38 ms 12432 KB Output is correct
21 Correct 36 ms 12256 KB Output is correct
22 Correct 44 ms 14352 KB Output is correct
23 Correct 33 ms 11924 KB Output is correct
24 Correct 32 ms 11976 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 3 ms 1796 KB Output is correct
4 Correct 2 ms 1804 KB Output is correct
5 Correct 2 ms 1804 KB Output is correct
6 Correct 3 ms 1796 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 1792 KB Output is correct
10 Correct 2 ms 1804 KB Output is correct
11 Correct 2 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 1800 KB Output is correct
15 Correct 2 ms 1800 KB Output is correct
16 Incorrect 2 ms 1796 KB Wrong Answer [6]
17 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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