# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246861 | SomeoneUnknown | Lokahian Relics (FXCUP4_lokahia) | C++17 | 5 ms | 640 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int getpar(int x){
//printf("getpar %d\n", x);
if(par[x] != x){
par[x] = getpar(par[x]);
}
return par[x];
}
int FindBase(int N){
//int par[N];
int disjointtotal = 0;
queue<int> ndjol; //not disjoint or lone
int curgrpsize = 1;
for(int i = 0; i < N; ++i){
par.push_back(i);
ndjol.push(i);
}
ndjol.push(N); //end of pairing
int llone = -1; //largest lone
while(ndjol.size() > 1){
int frst = ndjol.front();
ndjol.pop();
if(frst == N){
ndjol.push(N);
curgrpsize <<= 1;
continue;
}
frst = getpar(frst);
int scnd = ndjol.front();
ndjol.pop();
if(scnd == N){
ndjol.push(N);
curgrpsize <<= 1;
llone = frst;
continue;
}
scnd = getpar(scnd);
int res = frst;
if(frst != scnd) res = CollectRelics(frst, scnd);
if(res == -1){
disjointtotal += curgrpsize;
if(disjointtotal * 2 >= N){
return -1;
}
}else{
res = getpar(res);
par[frst] = res;
par[scnd] = res;
ndjol.push(res);
}
}
if(llone == -1){
return -1;
}
for(int i = 0; i < N; ++i){
if(i == llone || par[i] != i) continue;
int res = CollectRelics(i, llone);
if(res == -1) continue;
res = getpar(res);
par[llone] = res;
par[i] = res;
llone = res;
}
int llonesize = 0;
for(int i = 0; i < N; ++i){
if(getpar(i) == llone) llonesize++;
}
if(llonesize * 2 > N) return llone;
//CollectRelics()
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |