Submission #246861

#TimeUsernameProblemLanguageResultExecution timeMemory
246861SomeoneUnknownLokahian Relics (FXCUP4_lokahia)C++17
100 / 100
5 ms640 KiB
#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 timeMemoryGrader output
Fetching results...