oj.uz

Submission #320570

# Submission time Handle Problem Language Result Execution time Memory
320570 2020-11-09T06:13:34 Z seedkin Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 2 ms 768 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 FindBase(int N){
	// printf("%d\n", CollectRelics(0, 1));
	target = N / 2;

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

	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++) {
		for(int j = i+1; j< N; j++) {
			if(isRoot[i] ==0 || isRoot[j] == 0) continue;
			int one = i;
			int two = j;
			int r = CollectRelics(one, two);
			if( r == -1) {
				isRoot[one] = 1;
				isRoot[two] = 1;
				continue;
			}
			int num = findRoot(r, one);		
			num = findRoot(r, two);
			if(num >= target) return r;		
		}
	}

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 620 KB Partially correct : C = 445
2 Incorrect 1 ms 620 KB Wrong
3 Correct 1 ms 620 KB Correct : C = 30
4 Correct 1 ms 620 KB Correct : C = 295
5 Incorrect 1 ms 620 KB Wrong
6 Incorrect 1 ms 620 KB Wrong
7 Correct 1 ms 620 KB Correct : C = 50
8 Incorrect 1 ms 492 KB Wrong
9 Correct 1 ms 620 KB Correct : C = 215
10 Correct 1 ms 620 KB Correct : C = 30
11 Incorrect 2 ms 620 KB Wrong
12 Incorrect 1 ms 620 KB Wrong
13 Incorrect 2 ms 620 KB Wrong
14 Incorrect 1 ms 620 KB Wrong
15 Correct 1 ms 620 KB Correct : C = 219
16 Incorrect 1 ms 620 KB Wrong
17 Incorrect 1 ms 620 KB Wrong
18 Correct 2 ms 620 KB Correct : C = 50
19 Partially correct 1 ms 620 KB Partially correct : C = 496
20 Incorrect 0 ms 492 KB Wrong
21 Correct 1 ms 492 KB Correct : C = 1
22 Incorrect 1 ms 620 KB Wrong
23 Correct 1 ms 620 KB Correct : C = 194
24 Incorrect 1 ms 620 KB Wrong
25 Incorrect 1 ms 620 KB Wrong
26 Incorrect 1 ms 620 KB Wrong
27 Incorrect 1 ms 768 KB Wrong