oj.uz

Submission #234795

# Submission time Handle Problem Language Result Execution time Memory
234795 2020-05-25T16:19:14 Z medk Stray Cat (JOI20_stray) C++14
15 / 100
 77 ms 17348 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){
				trying=false;
				if(arr[prv]==0){
					prv=sq.back();
					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();
						prv=sq.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 57 ms 16120 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 47 ms 15460 KB Output is correct
4 Correct 73 ms 17348 KB Output is correct
5 Correct 71 ms 17120 KB Output is correct
6 Correct 55 ms 15816 KB Output is correct
7 Correct 55 ms 15980 KB Output is correct
8 Correct 68 ms 16652 KB Output is correct
9 Correct 65 ms 16792 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 16120 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 47 ms 15460 KB Output is correct
4 Correct 73 ms 17348 KB Output is correct
5 Correct 71 ms 17120 KB Output is correct
6 Correct 55 ms 15816 KB Output is correct
7 Correct 55 ms 15980 KB Output is correct
8 Correct 68 ms 16652 KB Output is correct
9 Correct 65 ms 16792 KB Output is correct
10 Correct 51 ms 13776 KB Output is correct
11 Correct 50 ms 13896 KB Output is correct
12 Correct 52 ms 13940 KB Output is correct
13 Correct 51 ms 13936 KB Output is correct
14 Correct 53 ms 14204 KB Output is correct
15 Correct 59 ms 14580 KB Output is correct
16 Correct 64 ms 16612 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13672 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 46 ms 13336 KB Output is correct
4 Correct 77 ms 14936 KB Output is correct
5 Correct 75 ms 15068 KB Output is correct
6 Correct 54 ms 13908 KB Output is correct
7 Correct 52 ms 13524 KB Output is correct
8 Correct 64 ms 14232 KB Output is correct
9 Correct 66 ms 14484 KB Output is correct
10 Correct 65 ms 14164 KB Output is correct
11 Correct 57 ms 14072 KB Output is correct
12 Correct 59 ms 14164 KB Output is correct
13 Correct 61 ms 14196 KB Output is correct
14 Correct 62 ms 14488 KB Output is correct
15 Correct 64 ms 14340 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13672 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 46 ms 13336 KB Output is correct
4 Correct 77 ms 14936 KB Output is correct
5 Correct 75 ms 15068 KB Output is correct
6 Correct 54 ms 13908 KB Output is correct
7 Correct 52 ms 13524 KB Output is correct
8 Correct 64 ms 14232 KB Output is correct
9 Correct 66 ms 14484 KB Output is correct
10 Correct 65 ms 14164 KB Output is correct
11 Correct 57 ms 14072 KB Output is correct
12 Correct 59 ms 14164 KB Output is correct
13 Correct 61 ms 14196 KB Output is correct
14 Correct 62 ms 14488 KB Output is correct
15 Correct 64 ms 14340 KB Output is correct
16 Correct 46 ms 12180 KB Output is correct
17 Correct 48 ms 12216 KB Output is correct
18 Correct 52 ms 12020 KB Output is correct
19 Correct 50 ms 11980 KB Output is correct
20 Correct 55 ms 12656 KB Output is correct
21 Correct 54 ms 12408 KB Output is correct
22 Correct 60 ms 14472 KB Output is correct
23 Correct 55 ms 12156 KB Output is correct
24 Correct 50 ms 12008 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1040 KB Output is correct
2 Correct 9 ms 780 KB Output is correct
3 Correct 10 ms 1124 KB Output is correct
4 Correct 10 ms 1136 KB Output is correct
5 Correct 10 ms 1140 KB Output is correct
6 Incorrect 10 ms 1128 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 11776 KB Output is correct
2 Incorrect 47 ms 12088 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 11964 KB Output is correct
2 Correct 54 ms 12200 KB Output is correct
3 Correct 9 ms 784 KB Output is correct
4 Correct 43 ms 11768 KB Output is correct
5 Correct 62 ms 12884 KB Output is correct
6 Incorrect 47 ms 11988 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -