oj.uz

Submission #234824

# Submission time Handle Problem Language Result Execution time Memory
234824 2020-05-25T18:14:44 Z medk Stray Cat (JOI20_stray) C++14
15 / 100
 72 ms 17344 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 56 ms 16124 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 47 ms 15424 KB Output is correct
4 Correct 69 ms 17112 KB Output is correct
5 Correct 71 ms 17344 KB Output is correct
6 Correct 57 ms 15852 KB Output is correct
7 Correct 55 ms 15952 KB Output is correct
8 Correct 66 ms 16664 KB Output is correct
9 Correct 66 ms 16644 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 16124 KB Output is correct
2 Correct 9 ms 1024 KB Output is correct
3 Correct 47 ms 15424 KB Output is correct
4 Correct 69 ms 17112 KB Output is correct
5 Correct 71 ms 17344 KB Output is correct
6 Correct 57 ms 15852 KB Output is correct
7 Correct 55 ms 15952 KB Output is correct
8 Correct 66 ms 16664 KB Output is correct
9 Correct 66 ms 16644 KB Output is correct
10 Correct 50 ms 13924 KB Output is correct
11 Correct 54 ms 13924 KB Output is correct
12 Correct 51 ms 13932 KB Output is correct
13 Correct 50 ms 13940 KB Output is correct
14 Correct 54 ms 14188 KB Output is correct
15 Correct 57 ms 14584 KB Output is correct
16 Correct 64 ms 16728 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13824 KB Output is correct
2 Correct 9 ms 1028 KB Output is correct
3 Correct 46 ms 13188 KB Output is correct
4 Correct 71 ms 14924 KB Output is correct
5 Correct 72 ms 14928 KB Output is correct
6 Correct 52 ms 13680 KB Output is correct
7 Correct 54 ms 13664 KB Output is correct
8 Correct 62 ms 14480 KB Output is correct
9 Correct 62 ms 14456 KB Output is correct
10 Correct 59 ms 14240 KB Output is correct
11 Correct 56 ms 14244 KB Output is correct
12 Correct 59 ms 14232 KB Output is correct
13 Correct 61 ms 14164 KB Output is correct
14 Correct 66 ms 14484 KB Output is correct
15 Correct 64 ms 14488 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13824 KB Output is correct
2 Correct 9 ms 1028 KB Output is correct
3 Correct 46 ms 13188 KB Output is correct
4 Correct 71 ms 14924 KB Output is correct
5 Correct 72 ms 14928 KB Output is correct
6 Correct 52 ms 13680 KB Output is correct
7 Correct 54 ms 13664 KB Output is correct
8 Correct 62 ms 14480 KB Output is correct
9 Correct 62 ms 14456 KB Output is correct
10 Correct 59 ms 14240 KB Output is correct
11 Correct 56 ms 14244 KB Output is correct
12 Correct 59 ms 14232 KB Output is correct
13 Correct 61 ms 14164 KB Output is correct
14 Correct 66 ms 14484 KB Output is correct
15 Correct 64 ms 14488 KB Output is correct
16 Correct 49 ms 12056 KB Output is correct
17 Correct 48 ms 12056 KB Output is correct
18 Correct 49 ms 11980 KB Output is correct
19 Correct 49 ms 12144 KB Output is correct
20 Correct 56 ms 12628 KB Output is correct
21 Correct 53 ms 12492 KB Output is correct
22 Correct 63 ms 14412 KB Output is correct
23 Correct 49 ms 12164 KB Output is correct
24 Correct 53 ms 12432 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1048 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 10 ms 1040 KB Output is correct
4 Correct 10 ms 1040 KB Output is correct
5 Correct 10 ms 1108 KB Output is correct
6 Correct 10 ms 1040 KB Output is correct
7 Correct 10 ms 1140 KB Output is correct
8 Correct 10 ms 1104 KB Output is correct
9 Correct 10 ms 1168 KB Output is correct
10 Correct 12 ms 1128 KB Output is correct
11 Correct 10 ms 1140 KB Output is correct
12 Correct 10 ms 1040 KB Output is correct
13 Correct 10 ms 1132 KB Output is correct
14 Correct 10 ms 1124 KB Output is correct
15 Correct 10 ms 1140 KB Output is correct
16 Correct 10 ms 1140 KB Output is correct
17 Correct 10 ms 1136 KB Output is correct
18 Runtime error 11 ms 1424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11852 KB Output is correct
2 Incorrect 48 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 48 ms 11928 KB Output is correct
2 Correct 52 ms 11988 KB Output is correct
3 Correct 9 ms 648 KB Output is correct
4 Correct 44 ms 11768 KB Output is correct
5 Correct 63 ms 12884 KB Output is correct
6 Correct 59 ms 12984 KB Output is correct
7 Correct 50 ms 12208 KB Output is correct
8 Incorrect 49 ms 11988 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -