oj.uz

Submission #234825

# Submission time Handle Problem Language Result Execution time Memory
234825 2020-05-25T18:17:49 Z medk Stray Cat (JOI20_stray) C++14
15 / 100
 74 ms 16856 KB 
#include <bits/stdc++.h>
#include "Anthony.h"

#define pb push_back
#define eb emplace_back

using namespace std;

int n,m;
vector<vector<pair<int,int>>> g;
vector<int> seq={0,1,0,0,1,1};

vector<int> Mark1();
vector<int> Mark2();

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V){
	n=N, m=M;
	g.resize(n);
	for(int i=0;i<m;i++){
		g[U[i]].eb(V[i],i);
		g[V[i]].eb(U[i],i);
	}
	if(A>=3) return Mark1();
	return Mark2();
}

vector<int> Mark1(){
	vector<int> dpth(n);
	vector<bool> vis(n);
	vector<int> ans(m);
	queue<int> bfs;
	bfs.push(0);
	dpth[0]=0;
	vis[0]=1;
	while(!bfs.empty()){
		int u=bfs.front();
		bfs.pop();
		for(auto p:g[u]){
			int v=p.first, e=p.second;
			if(!vis[v]){
				vis[v]=1;
				bfs.push(v);
				dpth[v]=dpth[u]+1;
				ans[e]=dpth[v]%3;
			}
			else{
				if(dpth[v]==dpth[u]) ans[e]=(dpth[v]+1)%3;
				else ans[e]=max(dpth[v],dpth[u])%3;
			}
		}
	}
	return ans;
}

vector<int> Mark2(){
	vector<bool> vis(n);
	vector<int> ans(m);
	queue<pair<int,int>> bfs;
	bfs.push({0,0});
	vis[0]=1;
	while(!bfs.empty()){
		int u=bfs.front().first, col=bfs.front().second;
		bfs.pop();
		for(auto p:g[u]){
			int v=p.first, e=p.second;
			if(vis[v]) continue;
			vis[v]=1;
			if(g[u].size()<=2){
				ans[e]=(col+1)%6;
				bfs.push({v,ans[e]});
			}
			else{
				ans[e]=seq[col]^1;
				bfs.push({v,ans[e]});
			}
		}
	}
	for(int i=0;i<m;i++) ans[i]=seq[ans[i]];
	return ans;
}
#include <bits/stdc++.h>
#include "Catherine.h"

#define pb push_back
#define x first
#define y second

using namespace std;

int a;
int prv=-1;
bool trying=true;
int cnt=0,revrem=0;
vector<int> sq;

void Init(int A, int B){
	a=A;
}

int Move1(vector<int> arr);
int Move2(vector<int> arr);

int Move(vector<int> arr){
	if(a>=3) return Move1(arr);
	return Move2(arr);
}

int Move1(vector<int> arr){
	set<int> st={0,1,2};
	for(int i=0;i<3;i++) if(arr[i]==0) st.erase(i);
	if(st.size()==1) return *st.begin();
	if(*next(st.begin())-*st.begin()==1) return *st.begin();
	return 2;
}

int Move2(vector<int> arr){
	if(trying){
		cnt++;
		if(cnt==1){
			int sum=arr[0]+arr[1];
			if(sum>2){
				trying=false;
				if(arr[0]==1){
					prv=0;
					return 0;
				}
				prv=1;
				return 1;
			}
			else{
				for(int i=0;i<arr[0];i++) sq.pb(0);
				for(int i=0;i<arr[1];i++) sq.pb(1);
				prv=sq.back();
				if(sum==1) trying=false;
				return prv;
			}
		}
		else{
			int sum=arr[0]+arr[1];
			if(sum>=2 || sum==0){
				trying=false;
				if(arr[prv]==0){
					sq.pop_back();
					revrem=cnt-2;
					return -1;
				}
				else{
					prv^=1;
					return prv;
				}
			}
			else{
				sq.pb((int)(arr[0]==0));
				if(cnt<4){
					prv=sq.back();
					return prv;
				}
				else{
					trying=false;
					if(sq==vector<int>{0,1,0,0,1} || sq==vector<int>{1,0,0,1,1} || sq==vector<int>{0,0,1,1,0} || sq==vector<int>{0,1,1,0,1} || sq==vector<int>{1,1,0,1,0} || sq==vector<int>{1,0,1,0,0}){
						sq.pop_back();
						sq.pop_back();
						revrem=2;
						return -1;
					}
					else{
						prv=sq.back();
						return prv;
					}
				}
			}
		}
	}
	if(revrem>0){
		revrem--;
		prv=sq.back();
		sq.pop_back();
		assert((int)sq.size()>0);
		return -1;
	}
	if(arr[0]+arr[1]==1){
		prv=(arr[0]==0);
		return prv;
	}
	//assert(arr[0]+arr[1]!=0);
	prv^=1;
	return prv;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15712 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 49 ms 15212 KB Output is correct
4 Correct 74 ms 16840 KB Output is correct
5 Correct 72 ms 16856 KB Output is correct
6 Correct 55 ms 15580 KB Output is correct
7 Correct 54 ms 15720 KB Output is correct
8 Correct 66 ms 16260 KB Output is correct
9 Correct 74 ms 16152 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15712 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 49 ms 15212 KB Output is correct
4 Correct 74 ms 16840 KB Output is correct
5 Correct 72 ms 16856 KB Output is correct
6 Correct 55 ms 15580 KB Output is correct
7 Correct 54 ms 15720 KB Output is correct
8 Correct 66 ms 16260 KB Output is correct
9 Correct 74 ms 16152 KB Output is correct
10 Correct 52 ms 13668 KB Output is correct
11 Correct 50 ms 13560 KB Output is correct
12 Correct 51 ms 13500 KB Output is correct
13 Correct 57 ms 13300 KB Output is correct
14 Correct 51 ms 13812 KB Output is correct
15 Correct 62 ms 14192 KB Output is correct
16 Correct 67 ms 16340 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13412 KB Output is correct
2 Correct 8 ms 772 KB Output is correct
3 Correct 45 ms 12820 KB Output is correct
4 Correct 68 ms 14704 KB Output is correct
5 Correct 68 ms 14680 KB Output is correct
6 Correct 51 ms 13412 KB Output is correct
7 Correct 52 ms 13392 KB Output is correct
8 Correct 66 ms 14232 KB Output is correct
9 Correct 65 ms 13980 KB Output is correct
10 Correct 59 ms 13908 KB Output is correct
11 Correct 59 ms 13720 KB Output is correct
12 Correct 63 ms 13720 KB Output is correct
13 Correct 59 ms 13564 KB Output is correct
14 Correct 64 ms 13976 KB Output is correct
15 Correct 65 ms 13948 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13412 KB Output is correct
2 Correct 8 ms 772 KB Output is correct
3 Correct 45 ms 12820 KB Output is correct
4 Correct 68 ms 14704 KB Output is correct
5 Correct 68 ms 14680 KB Output is correct
6 Correct 51 ms 13412 KB Output is correct
7 Correct 52 ms 13392 KB Output is correct
8 Correct 66 ms 14232 KB Output is correct
9 Correct 65 ms 13980 KB Output is correct
10 Correct 59 ms 13908 KB Output is correct
11 Correct 59 ms 13720 KB Output is correct
12 Correct 63 ms 13720 KB Output is correct
13 Correct 59 ms 13564 KB Output is correct
14 Correct 64 ms 13976 KB Output is correct
15 Correct 65 ms 13948 KB Output is correct
16 Correct 47 ms 11688 KB Output is correct
17 Correct 47 ms 11632 KB Output is correct
18 Correct 49 ms 11692 KB Output is correct
19 Correct 49 ms 11764 KB Output is correct
20 Correct 56 ms 12268 KB Output is correct
21 Correct 53 ms 12152 KB Output is correct
22 Correct 60 ms 14168 KB Output is correct
23 Correct 49 ms 11748 KB Output is correct
24 Correct 51 ms 11768 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1044 KB Output is correct
2 Correct 8 ms 780 KB Output is correct
3 Correct 10 ms 1260 KB Output is correct
4 Correct 11 ms 1260 KB Output is correct
5 Correct 10 ms 1136 KB Output is correct
6 Correct 10 ms 1136 KB Output is correct
7 Correct 11 ms 1132 KB Output is correct
8 Correct 10 ms 1260 KB Output is correct
9 Correct 10 ms 1140 KB Output is correct
10 Correct 10 ms 1124 KB Output is correct
11 Correct 10 ms 1104 KB Output is correct
12 Correct 10 ms 1132 KB Output is correct
13 Correct 11 ms 1084 KB Output is correct
14 Correct 10 ms 1128 KB Output is correct
15 Correct 10 ms 1248 KB Output is correct
16 Correct 10 ms 1124 KB Output is correct
17 Correct 10 ms 1264 KB Output is correct
18 Incorrect 10 ms 1132 KB Wrong Answer [5]
19 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11368 KB Output is correct
2 Incorrect 52 ms 11608 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11416 KB Output is correct
2 Correct 53 ms 11772 KB Output is correct
3 Correct 8 ms 1020 KB Output is correct
4 Correct 44 ms 11364 KB Output is correct
5 Correct 63 ms 12584 KB Output is correct
6 Correct 64 ms 12532 KB Output is correct
7 Correct 51 ms 11676 KB Output is correct
8 Incorrect 48 ms 11684 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -