oj.uz

답안 #320800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
320800 2020-11-10T01:17:07 Z seedkin 로카히아 유적 (FXCUP4_lokahia) C++17
0 / 100
 3 ms 1004 KB 
#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;
	int boss[205];
	int bossNum = 0;
	
	for(int i =0; i < N; i++) {
		root[i] = -1;
		select[i] = 1;
		isRoot[i] = 1;
		boss[i] = 0;
	}

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

	// a > b
	for(int i = bossNum; i--; ) {
		int a = boss[i];
		for(int j = i-1; j--; ) {
			int b = boss[j];
			int r = CollectRelics(a, b);
			if(r == -1) {
				for(int k = b+1; k < a-1; k++) {
					if(isRoot[k] == 0 ) continue;
					r = CollectRelics(a, k);
					if(r == -1) continue;
					int num = findRoot(r, a);
					num = findRoot(r, k);
					if(num >= target) return r;
				}
			} else {
				int num = findRoot(r, a);
				num = findRoot(r, b);
				if(num >= target) return r;
			}
		}
		except += getSelect(a, 0);
		if(N - except < target) return -1;
	}

	// for(int i =0; i < N; i++) {
	// 	if(isRoot[i] ==0) continue;
	// 	for(int j = i+1; j< N; j++) {
	// 		if(isRoot[j] == 0) continue;
	// 		int r = CollectRelics(i, j);
	// 		if( r == -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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 620 KB Wrong
2 Incorrect 2 ms 620 KB Wrong
3 Runtime error 3 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 2 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Incorrect 1 ms 620 KB Wrong
7 Runtime error 3 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 1 ms 620 KB Wrong
9 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 1 ms 640 KB Wrong
11 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 1 ms 620 KB Correct : C = 58
13 Incorrect 1 ms 620 KB Wrong
14 Incorrect 1 ms 620 KB Wrong
15 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 1 ms 620 KB Correct : C = 59
17 Correct 1 ms 620 KB Correct : C = 99
18 Correct 1 ms 492 KB Correct : C = 1
19 Runtime error 1 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 1 ms 620 KB Correct : C = 98
21 Incorrect 1 ms 620 KB Wrong
22 Runtime error 2 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Partially correct 3 ms 620 KB Partially correct : C = 376
24 Incorrect 1 ms 620 KB Wrong
25 Partially correct 1 ms 620 KB Partially correct : C = 376
26 Incorrect 1 ms 620 KB Wrong
27 Incorrect 2 ms 620 KB Wrong