oj.uz

Submission #320810

# Submission time Handle Problem Language Result Execution time Memory
320810 2020-11-10T01:44:38 Z seedkin Lokahian Relics (FXCUP4_lokahia) C++17
0 / 100
 2 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 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(i, 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]) continue;
		int r = CollectRelics(c, a);
		if(r == -1) {
			int b = boss[i+1];
			for(int j = a+1; j < b; j++) {
				if(root[j] == root[c]) continue;
				if(isRoot[j] == 0) continue;
				r = CollectRelics(c, j);
				if(r == -1) continue;
				int num = findRoot(c, j);				
				if(num > target) return r;
			}
			continue;
		}
		int num = findRoot(c, a);
		if(num > target) return r;
	}

	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Correct : C = 60
2 Runtime error 1 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 1 ms 620 KB Wrong
5 Correct 1 ms 620 KB Correct : C = 171
6 Correct 1 ms 620 KB Correct : C = 60
7 Incorrect 1 ms 620 KB Wrong
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 Runtime error 1 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 1 ms 620 KB Wrong
12 Incorrect 1 ms 620 KB Wrong
13 Runtime error 2 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 1 ms 620 KB Wrong
15 Correct 2 ms 620 KB Correct : C = 169
16 Correct 2 ms 768 KB Correct : C = 100
17 Correct 1 ms 620 KB Correct : C = 191
18 Incorrect 1 ms 620 KB Wrong
19 Runtime error 2 ms 1004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 1 ms 620 KB Wrong
21 Correct 1 ms 640 KB Correct : C = 59
22 Correct 1 ms 640 KB Correct : C = 2
23 Correct 1 ms 620 KB Correct : C = 100
24 Incorrect 1 ms 620 KB Wrong
25 Incorrect 1 ms 620 KB Wrong
26 Correct 1 ms 620 KB Correct : C = 99
27 Correct 1 ms 620 KB Correct : C = 111