#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 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;
return temp == -1 ? select[r]: findRoot(r, temp);
}
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;
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;
s++;
}
}
int c = boss[bossNum-1];
// for(int i =0; i < N; i++) {
// if(isRoot[i] == 0) continue;
// int r = CollectRelics(c, i);
// if(r== -1) continue;
// int num = findRoot(r, c);
// num = findRoot(r, i);
// if(num > target) return r;
// }
// 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(isRoot[j] == 0) 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[root[c]] > target) return root[c];
return -1;
}
