oj.uz

Submission #246851

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Correct : C = 60
2 Incorrect 5 ms 640 KB Wrong
3 Incorrect 5 ms 512 KB Wrong
4 Incorrect 5 ms 640 KB Wrong
5 Incorrect 5 ms 640 KB Wrong
6 Incorrect 5 ms 640 KB Wrong
7 Incorrect 5 ms 640 KB Wrong
8 Correct 5 ms 640 KB Correct : C = 105
9 Correct 5 ms 640 KB Correct : C = 101
10 Correct 5 ms 640 KB Correct : C = 63
11 Incorrect 4 ms 512 KB Wrong
12 Correct 5 ms 640 KB Correct : C = 106
13 Correct 6 ms 640 KB Correct : C = 106
14 Correct 5 ms 512 KB Correct : C = 60
15 Incorrect 5 ms 640 KB Wrong
16 Incorrect 5 ms 512 KB Wrong
17 Correct 5 ms 640 KB Correct : C = 117
18 Incorrect 5 ms 640 KB Wrong
19 Correct 7 ms 640 KB Correct : C = 100
20 Incorrect 5 ms 512 KB Wrong
21 Incorrect 5 ms 512 KB Wrong
22 Incorrect 5 ms 640 KB Wrong
23 Correct 5 ms 512 KB Correct : C = 60
24 Incorrect 5 ms 640 KB Wrong
25 Incorrect 5 ms 640 KB Wrong
26 Incorrect 5 ms 512 KB Wrong
27 Correct 5 ms 640 KB Correct : C = 100