제출 #246851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246851		SomeoneUnknown	로카히아 유적 (FXCUP4_lokahia)	C++17	0 / 100	7 ms	640 KiB

lokahia

#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int getpar(int 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();
        frst = getpar(frst);
        ndjol.pop();
        if(frst == N){
            ndjol.push(N);
            curgrpsize <<= 1;
            continue;
        }
        int scnd = ndjol.front();
        ndjol.pop();
        scnd = getpar(scnd);
        if(scnd == N){
            ndjol.push(N);
            curgrpsize <<= 1;
            llone = frst;
            continue;
        }
        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: 0 / 100