#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())
ll chk[210][210];
ll cou[210];
ll grp[210];
ll pa[210], ra[210];
ll cou2[210];
ll ffind(ll here)
{
if(here == pa[here])
return pa[here];
return pa[here] = ffind(pa[here]);
}
void uunion(ll X, ll Y)
{
X = ffind(X);
Y = ffind(Y);
if(X == Y)
return;
if(ra[X] < ra[Y])
pa[X] = Y;
else if(ra[Y] < ra[X])
pa[Y] = X;
else
{
pa[X] = Y;
ra[Y]++;
}
}
ll FindBase(ll N)
{
if(N <= 3)
return 1;
srand(time(NULL));
if(N <= 17)
{
for(ll i = 0 ; i < N ; i++)
{
for(ll j = i + 1 ; j < N ; j++)
{
ll gap = CollectRelics(i, j);
if(gap != -1)
{
grp[i] = gap;
grp[j] = gap;
}
}
}
for(ll i = 0 ; i < N ; i++)
cou[grp[i]]++;
ll maxx = 0, ans = 0;
for(ll i = 0 ; i < N ; i++)
{
if(maxx < cou[i])
{
maxx = cou[i];
ans = i;
}
}
if(maxx * 2 >= N)
return ans;
return -1;
}
for(ll i = 0 ; i < N ; i++)
pa[i] = i, ra[i] = 0, grp[i] = -1;
for(ll i = 0 ; i < 100 ; i++)
{
ll num1 = rand() % N, num2 = rand() % N;
ll coco = 0;
while(chk[num1][num2] || num1 == num2 || ffind(num1) == ffind(num2))
{
num1 = rand() % N;
num2 = rand() % N;
coco++;
if(coco >= 100000)
break;
}
if(coco >= 100000)
continue;
num1 = ffind(num1);
num2 = ffind(num2);
ll gap = CollectRelics(num1, num2);
chk[num1][num2] = chk[num2][num1] = 1;
if(gap != -1)
{
cou[gap]++;
grp[num1] = gap;
grp[num2] = gap;
grp[gap] = gap;
pa[num1] = gap;
pa[num2] = gap;
}
}
/*for(ll i = 0 ; i < N ; i++)
cou2[ffind(i)]++;
for(ll i = 0 ; i < N ; i++)
{
if(cou2[i] >= N / 2)
return i;
}*/
ll maxx = 0, sum = 0, ans = 0;
for(ll i = 0 ; i < N ; i++)
{
if(cou[i] > maxx)
{
maxx = cou[i];
ans = i;
}
sum += cou[i];
}
ll fff = 0;
ll coco = 0;
for(ll i = 0 ; i < N ; i++)
{
if(ans == i)
coco++;
else
{
ll gpgp = CollectRelics(i, ans);
if(gpgp == ans)
coco++;
}
}
if(coco >= N / 2)
return ans;
return -1;
}
Compilation message
lokahia.cpp: In function 'll FindBase(ll)':
lokahia.cpp:66:14: error: 'CollectRelics' was not declared in this scope
66 | ll gap = CollectRelics(i, j);
| ^~~~~~~~~~~~~
lokahia.cpp:120:12: error: 'CollectRelics' was not declared in this scope
120 | ll gap = CollectRelics(num1, num2);
| ^~~~~~~~~~~~~
lokahia.cpp:166:14: error: 'CollectRelics' was not declared in this scope
166 | ll gpgp = CollectRelics(i, ans);
| ^~~~~~~~~~~~~
lokahia.cpp:156:5: warning: unused variable 'fff' [-Wunused-variable]
156 | ll fff = 0;
| ^~~
