oj.uz

Submission #786036

# Submission time Handle Problem Language Result Execution time Memory
786036 2023-07-17T23:00:26 Z doowey Stray Cat (JOI20_stray) C++14
15 / 100
 39 ms 16588 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

namespace {

const int N = (int)20010;
vector<pii> T[N];
vector<int> pattern = {1,1,0,1,0,0};
int dd[N];

}  // namespace


int n, m;
vector<int> idx;
int dep[N];

void make1(){
	queue<int> que;
	for(int i = 0 ; i < n; i ++ ){
		dep[i]=-1;
	}
	for(int i = 0 ; i < m ; i ++ ){
		idx[i]=-1;
	}
	dep[0]=0;
	que.push(0);
	int nd;
	while(!que.empty()){
		nd=que.front();
		que.pop();
		for(auto x : T[nd]){
			if(dep[x.fi] == -1){
				dep[x.fi]=(dep[nd]+1)%3;
				que.push(x.fi);
			}
			if(idx[x.se] == -1) idx[x.se]=dep[nd];
			
		}
	}
}



void dfs0(int u, int par, int bit){
	vector<pii> nex;
	for(auto x : T[u]){
		if(x.fi == par) continue;
		nex.push_back(x);
	}
	if(nex.size() == 1){
		if(dd[u]==-1){
			dd[u]=0;
			while(pattern[dd[u]] != bit) dd[u] ++ ;
		}
		dd[nex[0].fi] = (dd[u] + 1) % 6;
		idx[nex[0].se] = pattern[nex[0].fi];
		dfs0(nex[0].fi, u, pattern[(dd[u] + 1) % 6]);
	}
	else{
		for(auto x : nex){
			idx[x.se] = bit ^ 1;
			dfs0(x.fi, u, bit ^ 1);
		}
	}
}

void make2(){
	for(int i = 0 ; i < n; i ++ ){
		dd[i]=-1;
	}
	dfs0(0, -1, 0);
}

vector<int> Mark(int _n, int _m, int a, int b, vector<int> u, vector<int> v) {
	n = _n;
	m = _m;
	for(int i = 0 ; i < m ; i ++ ){
		T[u[i]].push_back(mp(v[i],i));
		T[v[i]].push_back(mp(u[i],i));
	}
	idx.resize(m);
	if(a >= 3) make1();
	else make2();
	return idx;
}

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

namespace {

int A;
vector<int> trav;
int las;
bool know;

vector<int> pattern = {1, 1, 0, 1, 0, 0};

}  // namespace


void Init(int a, int b) {
	A = a;
	trav.clear();
	las = -1;
	know = false;
}

int move_3(vector<int> y){
	for(int d = 0; d < 3; d ++ ){
		if(y[d] > 0 && y[(d + 1) % 3] > 0) return d;
	}
	for(int d = 0; d < 3; d ++ ){
		if(y[d] > 0) return d;
	}
	return -1;
}

int move_2(vector<int> y){
	vector<int> g = y;
	if(las != -1) g[las] ++ ;
	
	int pick = -1;
	
	if(g[0] + g[1] != 2){
		know = true;
		trav.clear();
		if(g[0] == 1) pick = 0;
		else pick = 1;
	}
	else{
		if(know){
			if(!trav.empty()){
				pick = -1;
				las=trav.back();
				trav.pop_back();
			}
			else{
				if(y[0] == 1) pick = 0;
				else pick = 1;
				las=pick;
			}
		}
		else{
			if(trav.empty()){
				for(int d = 0; d < 2; d ++ ){
					for(int p = 0 ; p < y[d]; p ++ ){
						trav.push_back(d);
						pick=d;
						las=d;
					}
				}
			}
			else if(trav.size() <= 3){
				if(y[0]==1) pick=0;
				else pick=1;
				las = pick;
				trav.push_back(pick);
			}
			else{
				if(y[0] == 1) trav.push_back(0);
				else trav.push_back(1);
				bool rev = false;
				for(int i = 0 ; i < 6 ; i ++ ){
					vector<int> g;
					for(int j = 0 ; j < 5; j ++ ){
						g.push_back(pattern[(i + j) % 6]);
					}
					if(g == trav) rev = true;
				}
				if(rev == true){
					pick = -1;
					trav.pop_back();
					trav.erase(trav.begin());
					las = trav.back();
					trav.pop_back();
				}
				else{
					trav.clear();
					if(y[0] == 1) pick = 0;
					else pick = 1;
					las = pick;
				}
				
				know=true;
			}
		}
	}
	if(pick == -1 || y[pick] == 0) pick = -1;
	return pick;
}

int Move(std::vector<int> y) {
   if(A >= 3) return move_3(y);
   else{
	   return move_2(y);
   }
   return -1;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15604 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 24 ms 14804 KB Output is correct
4 Correct 36 ms 16500 KB Output is correct
5 Correct 34 ms 16588 KB Output is correct
6 Correct 27 ms 15404 KB Output is correct
7 Correct 32 ms 15384 KB Output is correct
8 Correct 32 ms 16020 KB Output is correct
9 Correct 32 ms 15892 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15604 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 24 ms 14804 KB Output is correct
4 Correct 36 ms 16500 KB Output is correct
5 Correct 34 ms 16588 KB Output is correct
6 Correct 27 ms 15404 KB Output is correct
7 Correct 32 ms 15384 KB Output is correct
8 Correct 32 ms 16020 KB Output is correct
9 Correct 32 ms 15892 KB Output is correct
10 Correct 25 ms 13412 KB Output is correct
11 Correct 25 ms 13464 KB Output is correct
12 Correct 30 ms 13316 KB Output is correct
13 Correct 26 ms 13304 KB Output is correct
14 Correct 27 ms 13664 KB Output is correct
15 Correct 28 ms 14020 KB Output is correct
16 Correct 39 ms 16020 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13132 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 24 ms 12788 KB Output is correct
4 Correct 33 ms 14464 KB Output is correct
5 Correct 32 ms 14416 KB Output is correct
6 Correct 26 ms 13092 KB Output is correct
7 Correct 26 ms 13160 KB Output is correct
8 Correct 33 ms 13688 KB Output is correct
9 Correct 33 ms 13644 KB Output is correct
10 Correct 27 ms 13468 KB Output is correct
11 Correct 31 ms 13476 KB Output is correct
12 Correct 27 ms 13412 KB Output is correct
13 Correct 28 ms 13408 KB Output is correct
14 Correct 33 ms 13884 KB Output is correct
15 Correct 30 ms 13804 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13132 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 24 ms 12788 KB Output is correct
4 Correct 33 ms 14464 KB Output is correct
5 Correct 32 ms 14416 KB Output is correct
6 Correct 26 ms 13092 KB Output is correct
7 Correct 26 ms 13160 KB Output is correct
8 Correct 33 ms 13688 KB Output is correct
9 Correct 33 ms 13644 KB Output is correct
10 Correct 27 ms 13468 KB Output is correct
11 Correct 31 ms 13476 KB Output is correct
12 Correct 27 ms 13412 KB Output is correct
13 Correct 28 ms 13408 KB Output is correct
14 Correct 33 ms 13884 KB Output is correct
15 Correct 30 ms 13804 KB Output is correct
16 Correct 25 ms 11616 KB Output is correct
17 Correct 23 ms 11616 KB Output is correct
18 Correct 24 ms 11440 KB Output is correct
19 Correct 24 ms 11560 KB Output is correct
20 Correct 27 ms 12156 KB Output is correct
21 Correct 27 ms 11948 KB Output is correct
22 Correct 28 ms 13904 KB Output is correct
23 Correct 25 ms 11592 KB Output is correct
24 Correct 25 ms 11600 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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