Submission #246861

#	Time	Username	Problem	Language	Result	Execution time	Memory
246861		SomeoneUnknown	Lokahian Relics (FXCUP4_lokahia)	C++17	100 / 100	5 ms	640 KiB

lokahia

#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;
}

• Subtask 1: 100 / 100