oj.uz

Submission #320922

# Submission time Handle Problem Language Result Execution time Memory
320922 2020-11-10T09:08:14 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;
	findRoot(r, 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++) {
            if(getRoot(i) == getRoot(j)) continue;
			int r = CollectRelics(getRoot(i), getRoot(j));
			if( r == -1) {
				s--;
				if(s == 0) {
					i = j+1;
					if(i == N) return -1;
					break;
				}
				continue;
			}
			int num = findRoot(getRoot(r), getRoot(i));
			num = findRoot(getRoot(r),getRoot(j));
			if(num > target) return getRoot(r);
			s++;
		}
	}
 
	int c = boss[bossNum-1];
 
	// for(int i =0; i < bossNum-1; i++) {
	// 	int a = boss[i];		
    //     if(getRoot(c) == getRoot(a)) continue;
	// 	int r = CollectRelics(getRoot(c), getRoot(a));
	// 	if(r == -1) {
	// 		int b = boss[i+1];
	// 		for(int j = a+1; j < b; j++) {
    //             if(getRoot(c) == getRoot(j)) continue;
	// 			if(getRoot(j) != j) continue;
	// 			r = CollectRelics(getRoot(c), getRoot(j));
	// 			if(r == -1) continue;
	// 			int num = findRoot(getRoot(r), getRoot(c));
	// 			num = findRoot(getRoot(r), getRoot(j));
	// 			if(num > target) return getRoot(r);
	// 		}
	// 		continue;
	// 	}
	// 	int num = findRoot(getRoot(r), getRoot(c));
	// 	num = findRoot(getRoot(r), getRoot(a));
	// 	if(num > target) return getRoot(r);
	// }
 
	if(select[getRoot(c)] > target ) return getRoot(c);    
	return -1;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Correct : C = 115
2 Correct 1 ms 620 KB Correct : C = 170
3 Correct 1 ms 620 KB Correct : C = 187
4 Execution timed out 1086 ms 620 KB Time limit exceeded
5 Correct 1 ms 492 KB Correct : C = 58
6 Correct 1 ms 620 KB Correct : C = 100
7 Correct 1 ms 492 KB Correct : C = 59
8 Correct 1 ms 492 KB Correct : C = 2
9 Correct 1 ms 492 KB Correct : C = 60
10 Correct 1 ms 492 KB Correct : C = 102
11 Correct 2 ms 620 KB Correct : C = 98
12 Execution timed out 1087 ms 492 KB Time limit exceeded
13 Correct 1 ms 620 KB Correct : C = 168
14 Execution timed out 1064 ms 620 KB Time limit exceeded
15 Execution timed out 1090 ms 492 KB Time limit exceeded
16 Execution timed out 1047 ms 620 KB Time limit exceeded
17 Execution timed out 1089 ms 620 KB Time limit exceeded
18 Correct 1 ms 620 KB Correct : C = 99
19 Execution timed out 1088 ms 620 KB Time limit exceeded
20 Incorrect 1 ms 620 KB Wrong
21 Incorrect 1 ms 620 KB Wrong
22 Incorrect 1 ms 492 KB Wrong
23 Correct 1 ms 620 KB Correct : C = 111
24 Execution timed out 1046 ms 492 KB Time limit exceeded
25 Execution timed out 1072 ms 492 KB Time limit exceeded
26 Execution timed out 1087 ms 620 KB Time limit exceeded
27 Incorrect 1 ms 620 KB Wrong