제출 #320580

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
320580		seedkin	로카히아 유적 (FXCUP4_lokahia)	C++17	0 / 100	2 ms	768 KiB

lokahia

#include "lokahia.h"
#include <stdio.h>

int root[205]; // who is root?
int select[205]; // able to get mana?
int isRoot[205]; // 1== root 0 == no
int target;

int findRoot(int r, int leaf) {
	if(r == leaf) return select[r];

	int temp = root[leaf];
	select[r] += select[leaf];
	root[leaf] = r;
	select[leaf] = 0;
	isRoot[leaf] = 0;
	// isRoot[r] = 1;

	return temp == -1 ? select[r]: findRoot(r, temp);
}

int getSelect(int n, int d) {
	if(root[n] != -1) return getSelect(root[n], d);
	isRoot[n] = d;
	return select[n];
}

int FindBase(int N){
	// printf("%d\n", CollectRelics(0, 1));
	target = N / 2;
	int except = 0;
	

	for(int i =0; i < N; i++) {
		root[i] = -1;
		select[i] = 1;
		isRoot[i] = 1;
	}

	// if(N % 2) isRoot[N-1] = 1;

	// for(int i =0; i+1 < N; i+=2) {
	// 	int r = CollectRelics(i, i+1);
	// 	if( r == -1) {
	// 		isRoot[i] = 1;
	// 		isRoot[i+1] = 1;
	// 		continue;
	// 	}
	// 	int num = findRoot(r, i);		
	// 	num = findRoot(r, i+1);
	// 	if(num >= target) return r;		
	// }

	for(int i =0; i < N; i++) {
		if(isRoot[i] ==0) continue;
		int e = 0;
		for(int j = i+1; j< N; j++) {
			if(isRoot[j] == 0) continue;
			if(N - e < target) break;
			int r = CollectRelics(i, j);
			if( r == -1) {
				e += getSelect(j, 1);
				continue;
			}
			int num = findRoot(r, i);		
			num = findRoot(r, j);
			if(num >= target) return r;
		}
		except += getSelect(i, 0);
		if(N - except < target) return -1;
	}

	// for(int i =0; i< N; i++) {
	// 	printf("node: %d select: %d\n", i, select[i]);
	// }
	return -1;
}

• Subtask 1: 0 / 100