#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
