oj.uz

Submission #234805

# Submission time Handle Problem Language Result Execution time Memory
234805 2020-05-25T17:19:32 Z medk Stray Cat (JOI20_stray) C++14
15 / 100
 76 ms 17116 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(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();
		return -1;
	}
	if(arr[0]+arr[1]==1){
		prv=(arr[0]==0);
		return prv;
	}
	prv^=1;
	return prv;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16104 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 47 ms 15444 KB Output is correct
4 Correct 72 ms 16864 KB Output is correct
5 Correct 72 ms 17116 KB Output is correct
6 Correct 57 ms 16192 KB Output is correct
7 Correct 55 ms 15832 KB Output is correct
8 Correct 70 ms 16588 KB Output is correct
9 Correct 70 ms 16636 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16104 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 47 ms 15444 KB Output is correct
4 Correct 72 ms 16864 KB Output is correct
5 Correct 72 ms 17116 KB Output is correct
6 Correct 57 ms 16192 KB Output is correct
7 Correct 55 ms 15832 KB Output is correct
8 Correct 70 ms 16588 KB Output is correct
9 Correct 70 ms 16636 KB Output is correct
10 Correct 51 ms 14028 KB Output is correct
11 Correct 51 ms 13896 KB Output is correct
12 Correct 51 ms 13936 KB Output is correct
13 Correct 51 ms 13940 KB Output is correct
14 Correct 53 ms 14200 KB Output is correct
15 Correct 62 ms 14540 KB Output is correct
16 Correct 64 ms 16596 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13700 KB Output is correct
2 Correct 9 ms 892 KB Output is correct
3 Correct 45 ms 13344 KB Output is correct
4 Correct 76 ms 14940 KB Output is correct
5 Correct 73 ms 14924 KB Output is correct
6 Correct 52 ms 13776 KB Output is correct
7 Correct 62 ms 13664 KB Output is correct
8 Correct 63 ms 14484 KB Output is correct
9 Correct 62 ms 14484 KB Output is correct
10 Correct 60 ms 14236 KB Output is correct
11 Correct 56 ms 14228 KB Output is correct
12 Correct 57 ms 14236 KB Output is correct
13 Correct 56 ms 14240 KB Output is correct
14 Correct 62 ms 14612 KB Output is correct
15 Correct 62 ms 14480 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13700 KB Output is correct
2 Correct 9 ms 892 KB Output is correct
3 Correct 45 ms 13344 KB Output is correct
4 Correct 76 ms 14940 KB Output is correct
5 Correct 73 ms 14924 KB Output is correct
6 Correct 52 ms 13776 KB Output is correct
7 Correct 62 ms 13664 KB Output is correct
8 Correct 63 ms 14484 KB Output is correct
9 Correct 62 ms 14484 KB Output is correct
10 Correct 60 ms 14236 KB Output is correct
11 Correct 56 ms 14228 KB Output is correct
12 Correct 57 ms 14236 KB Output is correct
13 Correct 56 ms 14240 KB Output is correct
14 Correct 62 ms 14612 KB Output is correct
15 Correct 62 ms 14480 KB Output is correct
16 Correct 46 ms 12108 KB Output is correct
17 Correct 47 ms 12088 KB Output is correct
18 Correct 51 ms 12124 KB Output is correct
19 Correct 49 ms 12272 KB Output is correct
20 Correct 56 ms 12660 KB Output is correct
21 Correct 55 ms 12656 KB Output is correct
22 Correct 62 ms 14436 KB Output is correct
23 Correct 50 ms 12156 KB Output is correct
24 Correct 49 ms 12152 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1108 KB Output is correct
2 Correct 9 ms 792 KB Output is correct
3 Correct 10 ms 1124 KB Output is correct
4 Correct 10 ms 1104 KB Output is correct
5 Correct 10 ms 1124 KB Output is correct
6 Correct 10 ms 1048 KB Output is correct
7 Correct 10 ms 1116 KB Output is correct
8 Correct 11 ms 1124 KB Output is correct
9 Correct 10 ms 1108 KB Output is correct
10 Correct 10 ms 1264 KB Output is correct
11 Correct 10 ms 1132 KB Output is correct
12 Correct 10 ms 1124 KB Output is correct
13 Correct 10 ms 1048 KB Output is correct
14 Correct 10 ms 1100 KB Output is correct
15 Correct 10 ms 1124 KB Output is correct
16 Correct 10 ms 1128 KB Output is correct
17 Correct 10 ms 1104 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 11920 KB Output is correct
2 Incorrect 49 ms 12100 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11856 KB Output is correct
2 Correct 52 ms 12040 KB Output is correct
3 Correct 8 ms 1012 KB Output is correct
4 Correct 45 ms 11572 KB Output is correct
5 Correct 59 ms 12976 KB Output is correct
6 Correct 61 ms 12800 KB Output is correct
7 Correct 51 ms 11988 KB Output is correct
8 Incorrect 51 ms 12336 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -