oj.uz

Submission #320836

# Submission time Handle Problem Language Result Execution time Memory
320836 2020-11-10T05:04:30 Z seedkin Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 1000 ms 620 KB 
#include "lokahia.h"
#include <stdio.h>

int root[205]; // who is root?
int select[205]; // able to get mana?

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;	

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

int getRoot(int n) {
	int r = root[n];
	if(r == -1) return n;
	root[n] = getRoot(r);
	return root[n];
}
int FindBase(int N){	
	int target = N / 2;	
	int boss[205];
	int bossNum = 0;
	
	for(int i =0; i < N; i++) {
		root[i] = -1;
		select[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;
					if(i == N) return -1;
					break;
				}
				continue;
			}
			int num = findRoot(r, i);
			num = findRoot(r,j);
			if(num > target) return r;
			s++;
		}
	}

	int c = boss[bossNum-1];

	// for(int i =0; i < bossNum-1; i++) {
	// 	int a = boss[i];
	// 	if(root[c] == root[a] && root[c] != -1) continue;
	// 	int r = CollectRelics(c, a);
	// 	if(r == -1) {
	// 		int b = boss[i+1];
	// 		for(int j = a+1; j < b; j++) {
	// 			if(root[c] == root[j] && root[c] != -1) continue;
	// 			if(root[j] != -1) continue;
	// 			r = CollectRelics(c, j);
	// 			if(r == -1) continue;
	// 			int num = findRoot(r, c);
	// 			num = findRoot(r, j);
	// 			if(num > target) return r;
	// 		}
	// 		continue;
	// 	}
	// 	int num = findRoot(r, c);
	// 	num = findRoot(r, a);
	// 	if(num > target) return r;
	// }

	if(root[c] == -1 && select[c] > target ) return c;
	else if(root[c] != -1 && select[getRoot(c)] > target) return root[c];
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB Wrong
2 Correct 1 ms 620 KB Correct : C = 99
3 Correct 1 ms 620 KB Correct : C = 103
4 Correct 1 ms 492 KB Correct : C = 2
5 Incorrect 1 ms 620 KB Wrong
6 Incorrect 1 ms 492 KB Wrong
7 Correct 1 ms 492 KB Correct : C = 60
8 Correct 1 ms 620 KB Correct : C = 100
9 Correct 1 ms 620 KB Correct : C = 111
10 Incorrect 1 ms 620 KB Wrong
11 Execution timed out 1089 ms 620 KB Time limit exceeded
12 Incorrect 1 ms 620 KB Wrong
13 Correct 1 ms 492 KB Correct : C = 59
14 Correct 1 ms 620 KB Correct : C = 171
15 Execution timed out 1098 ms 620 KB Time limit exceeded
16 Execution timed out 1096 ms 492 KB Time limit exceeded
17 Correct 1 ms 620 KB Correct : C = 191
18 Correct 1 ms 620 KB Correct : C = 60
19 Execution timed out 1037 ms 620 KB Time limit exceeded
20 Incorrect 1 ms 492 KB Wrong
21 Execution timed out 1097 ms 492 KB Time limit exceeded
22 Incorrect 1 ms 620 KB Wrong
23 Correct 1 ms 620 KB Correct : C = 169
24 Correct 1 ms 620 KB Correct : C = 100
25 Incorrect 1 ms 620 KB Wrong
26 Execution timed out 1046 ms 492 KB Time limit exceeded
27 Incorrect 1 ms 620 KB Wrong