oj.uz

답안 #786038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786038 2023-07-17T23:02:24 Z doowey 길고양이 (JOI20_stray) C++14
15 / 100
 36 ms 16564 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[dd[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

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 15588 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 23 ms 14752 KB Output is correct
4 Correct 34 ms 16560 KB Output is correct
5 Correct 36 ms 16564 KB Output is correct
6 Correct 27 ms 15336 KB Output is correct
7 Correct 27 ms 15376 KB Output is correct
8 Correct 34 ms 16032 KB Output is correct
9 Correct 32 ms 15980 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 15588 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 23 ms 14752 KB Output is correct
4 Correct 34 ms 16560 KB Output is correct
5 Correct 36 ms 16564 KB Output is correct
6 Correct 27 ms 15336 KB Output is correct
7 Correct 27 ms 15376 KB Output is correct
8 Correct 34 ms 16032 KB Output is correct
9 Correct 32 ms 15980 KB Output is correct
10 Correct 28 ms 13464 KB Output is correct
11 Correct 25 ms 13528 KB Output is correct
12 Correct 25 ms 13488 KB Output is correct
13 Correct 26 ms 13400 KB Output is correct
14 Correct 28 ms 13672 KB Output is correct
15 Correct 28 ms 13940 KB Output is correct
16 Correct 31 ms 16048 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 13128 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 22 ms 12788 KB Output is correct
4 Correct 33 ms 14392 KB Output is correct
5 Correct 32 ms 14440 KB Output is correct
6 Correct 26 ms 13104 KB Output is correct
7 Correct 26 ms 13160 KB Output is correct
8 Correct 30 ms 13672 KB Output is correct
9 Correct 30 ms 13660 KB Output is correct
10 Correct 28 ms 13412 KB Output is correct
11 Correct 27 ms 13416 KB Output is correct
12 Correct 28 ms 13448 KB Output is correct
13 Correct 27 ms 13360 KB Output is correct
14 Correct 30 ms 13792 KB Output is correct
15 Correct 30 ms 13832 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 13128 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 22 ms 12788 KB Output is correct
4 Correct 33 ms 14392 KB Output is correct
5 Correct 32 ms 14440 KB Output is correct
6 Correct 26 ms 13104 KB Output is correct
7 Correct 26 ms 13160 KB Output is correct
8 Correct 30 ms 13672 KB Output is correct
9 Correct 30 ms 13660 KB Output is correct
10 Correct 28 ms 13412 KB Output is correct
11 Correct 27 ms 13416 KB Output is correct
12 Correct 28 ms 13448 KB Output is correct
13 Correct 27 ms 13360 KB Output is correct
14 Correct 30 ms 13792 KB Output is correct
15 Correct 30 ms 13832 KB Output is correct
16 Correct 26 ms 11616 KB Output is correct
17 Correct 23 ms 11544 KB Output is correct
18 Correct 24 ms 11484 KB Output is correct
19 Correct 24 ms 11508 KB Output is correct
20 Correct 32 ms 12092 KB Output is correct
21 Correct 26 ms 11864 KB Output is correct
22 Correct 30 ms 13972 KB Output is correct
23 Correct 25 ms 11628 KB Output is correct
24 Correct 26 ms 11464 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1292 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct
3 Correct 1 ms 1284 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1412 KB Output is correct
6 Correct 2 ms 1420 KB Output is correct
7 Correct 2 ms 1420 KB Output is correct
8 Correct 2 ms 1412 KB Output is correct
9 Correct 2 ms 1412 KB Output is correct
10 Correct 2 ms 1416 KB Output is correct
11 Correct 2 ms 1420 KB Output is correct
12 Incorrect 2 ms 1412 KB Wrong Answer [6]
13 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 11264 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 11220 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -