oj.uz

답안 #786044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
786044 2023-07-17T23:11:07 Z doowey 길고양이 (JOI20_stray) C++14
20 / 100
 44 ms 16540 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;
		las = pick;
	}
	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 < 4; 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 28 ms 15508 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 24 ms 14924 KB Output is correct
4 Correct 34 ms 16540 KB Output is correct
5 Correct 33 ms 16528 KB Output is correct
6 Correct 27 ms 15328 KB Output is correct
7 Correct 31 ms 15284 KB Output is correct
8 Correct 34 ms 15940 KB Output is correct
9 Correct 31 ms 16032 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 15508 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 24 ms 14924 KB Output is correct
4 Correct 34 ms 16540 KB Output is correct
5 Correct 33 ms 16528 KB Output is correct
6 Correct 27 ms 15328 KB Output is correct
7 Correct 31 ms 15284 KB Output is correct
8 Correct 34 ms 15940 KB Output is correct
9 Correct 31 ms 16032 KB Output is correct
10 Correct 25 ms 13412 KB Output is correct
11 Correct 25 ms 13412 KB Output is correct
12 Correct 26 ms 13320 KB Output is correct
13 Correct 25 ms 13328 KB Output is correct
14 Correct 26 ms 13632 KB Output is correct
15 Correct 30 ms 14128 KB Output is correct
16 Correct 32 ms 16092 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 13168 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 25 ms 12740 KB Output is correct
4 Correct 32 ms 14432 KB Output is correct
5 Correct 38 ms 14328 KB Output is correct
6 Correct 26 ms 13092 KB Output is correct
7 Correct 26 ms 13064 KB Output is correct
8 Correct 32 ms 13668 KB Output is correct
9 Correct 28 ms 13680 KB Output is correct
10 Correct 27 ms 13448 KB Output is correct
11 Correct 28 ms 13508 KB Output is correct
12 Correct 30 ms 13460 KB Output is correct
13 Correct 32 ms 13484 KB Output is correct
14 Correct 39 ms 13856 KB Output is correct
15 Correct 30 ms 13784 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 13168 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 25 ms 12740 KB Output is correct
4 Correct 32 ms 14432 KB Output is correct
5 Correct 38 ms 14328 KB Output is correct
6 Correct 26 ms 13092 KB Output is correct
7 Correct 26 ms 13064 KB Output is correct
8 Correct 32 ms 13668 KB Output is correct
9 Correct 28 ms 13680 KB Output is correct
10 Correct 27 ms 13448 KB Output is correct
11 Correct 28 ms 13508 KB Output is correct
12 Correct 30 ms 13460 KB Output is correct
13 Correct 32 ms 13484 KB Output is correct
14 Correct 39 ms 13856 KB Output is correct
15 Correct 30 ms 13784 KB Output is correct
16 Correct 23 ms 11620 KB Output is correct
17 Correct 24 ms 11588 KB Output is correct
18 Correct 30 ms 11472 KB Output is correct
19 Correct 25 ms 11508 KB Output is correct
20 Correct 26 ms 12216 KB Output is correct
21 Correct 26 ms 11956 KB Output is correct
22 Correct 28 ms 13920 KB Output is correct
23 Correct 25 ms 11536 KB Output is correct
24 Correct 25 ms 11612 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1292 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 1 ms 1284 KB Output is correct
4 Correct 2 ms 1420 KB Output is correct
5 Correct 2 ms 1420 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 1416 KB Output is correct
9 Correct 2 ms 1420 KB Output is correct
10 Correct 2 ms 1412 KB Output is correct
11 Correct 2 ms 1420 KB Output is correct
12 Correct 2 ms 1412 KB Output is correct
13 Correct 2 ms 1420 KB Output is correct
14 Correct 2 ms 1420 KB Output is correct
15 Correct 2 ms 1420 KB Output is correct
16 Correct 2 ms 1284 KB Output is correct
17 Correct 2 ms 1284 KB Output is correct
18 Correct 2 ms 1284 KB Output is correct
19 Correct 2 ms 1284 KB Output is correct
20 Correct 2 ms 1296 KB Output is correct
21 Correct 2 ms 1284 KB Output is correct
22 Correct 2 ms 1284 KB Output is correct
23 Correct 2 ms 1284 KB Output is correct
24 Correct 2 ms 1288 KB Output is correct
25 Correct 2 ms 1284 KB Output is correct
26 Correct 2 ms 1292 KB Output is correct
27 Correct 2 ms 1292 KB Output is correct
28 Correct 2 ms 1284 KB Output is correct

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11228 KB Output is correct
2 Correct 27 ms 13180 KB Output is correct
3 Correct 1 ms 1036 KB Output is correct
4 Correct 20 ms 11216 KB Output is correct
5 Correct 44 ms 15464 KB Output is correct
6 Correct 32 ms 15544 KB Output is correct
7 Correct 27 ms 14528 KB Output is correct
8 Correct 27 ms 14512 KB Output is correct
9 Correct 32 ms 15464 KB Output is correct
10 Correct 44 ms 15480 KB Output is correct
11 Correct 34 ms 15380 KB Output is correct
12 Correct 32 ms 15464 KB Output is correct
13 Correct 39 ms 15492 KB Output is correct
14 Correct 31 ms 15468 KB Output is correct
15 Correct 31 ms 15456 KB Output is correct
16 Correct 39 ms 15376 KB Output is correct
17 Correct 30 ms 15172 KB Output is correct
18 Incorrect 28 ms 15116 KB Wrong Answer [6]
19 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 11296 KB Output is correct
2 Correct 26 ms 13176 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 20 ms 11220 KB Output is correct
5 Correct 32 ms 15500 KB Output is correct
6 Correct 38 ms 15556 KB Output is correct
7 Correct 30 ms 14452 KB Output is correct
8 Incorrect 25 ms 14508 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -