oj.uz

Submission #246861

# Submission time Handle Problem Language Result Execution time Memory
246861 2020-07-10T12:27:59 Z SomeoneUnknown Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 5 ms 640 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correct : C = 60
2 Correct 5 ms 512 KB Correct : C = 150
3 Correct 5 ms 512 KB Correct : C = 136
4 Correct 5 ms 512 KB Correct : C = 3
5 Correct 5 ms 512 KB Correct : C = 147
6 Correct 5 ms 512 KB Correct : C = 177
7 Correct 5 ms 640 KB Correct : C = 60
8 Correct 5 ms 640 KB Correct : C = 210
9 Correct 5 ms 640 KB Correct : C = 230
10 Correct 5 ms 512 KB Correct : C = 60
11 Correct 5 ms 640 KB Correct : C = 147
12 Correct 5 ms 640 KB Correct : C = 243
13 Correct 5 ms 640 KB Correct : C = 117
14 Correct 5 ms 640 KB Correct : C = 100
15 Correct 5 ms 640 KB Correct : C = 243
16 Correct 5 ms 512 KB Correct : C = 129
17 Correct 5 ms 640 KB Correct : C = 105
18 Correct 5 ms 640 KB Correct : C = 100
19 Correct 5 ms 640 KB Correct : C = 250
20 Correct 5 ms 640 KB Correct : C = 230
21 Correct 5 ms 512 KB Correct : C = 0
22 Correct 5 ms 640 KB Correct : C = 241
23 Correct 5 ms 512 KB Correct : C = 150
24 Correct 5 ms 640 KB Correct : C = 269
25 Correct 5 ms 640 KB Correct : C = 100
26 Correct 5 ms 640 KB Correct : C = 297
27 Correct 5 ms 640 KB Correct : C = 229