oj.uz

Submission #150313

# Submission time Handle Problem Language Result Execution time Memory
150313 2019-09-01T08:07:12 Z Cafe Maru(#3599, bryan, pps789, kazel) Lokahian Relics (FXCUP4_lokahia) C++17
100 / 100
 8 ms 768 KB 
#include "lokahia.h"
#include<algorithm>
#include<vector>

const int NMAX = 200;

int p[NMAX];
std::vector<int> child[NMAX];

int Find(int u){return p[u];}

bool Merge(int u, int v, int c){
    u = Find(u), v = Find(v), c = Find(c);
    if(u==v && v==c) return false;
    if(u==v){
        for(int x:child[u]){
            p[x] = c;
            child[c].push_back(x);
        }
    }
    else if(c==u){
        for(int x:child[v]){
            p[x] = u;
            child[u].push_back(x);
        }
    }
    else if(c==v){
        for(int x:child[u]){
            p[x] = v;
            child[v].push_back(x);
        }
    }
    else{
        for(int x:child[u]){
            p[x] = c;
            child[c].push_back(x);
        }
        for(int x:child[v]){
            p[x] = c;
            child[c].push_back(x);
        }
    }
    return true;
}


int cache[NMAX][NMAX]; // init by -2
int COUNT = 0;
const int LIMIT = 300;
int CR(int u, int v){
    u=Find(u), v=Find(v);
    if(u==v) return u;
    if(u>v) std::swap(u,v);
    if(cache[u][v]!=-2) return cache[u][v];

    if(COUNT>=LIMIT) return -1;
    COUNT++;
    return cache[u][v] = CollectRelics(u,v);
}

int FindBase(int N){
    if(N==1) return 0;
    for(int i=0;i<N;i++) child[i].push_back(i), p[i]=i;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cache[i][j] = -2;

    while(1){
        std::vector<int> roots;
        for(int i=0;i<N;i++) if(Find(i)==i) roots.push_back(i);
        std::random_shuffle(roots.begin(), roots.end());

        std::vector<int> reals;
        for(int root:roots){
            std::random_shuffle(child[root].begin(), child[root].end());
            for(int c:child[root]) reals.push_back(c);
        }

        std::vector<int> L, R;
        int sz = N/2;
        for(int i=0;i<sz;i++) L.push_back(reals[i]);
        for(int i=sz;i<sz+sz;i++) R.push_back(reals[i]);

        bool all_false = true;
        for(int i=0;i<sz;i++){
            int u = L[i], v = R[i];
            int c = CR(u, v);
            if(c!=-1){
                if(Merge(u, v, c)) all_false = false;
            }
        }
        if(N%2){
            int last = reals.back();
            int l = L.back(), r = R.back();
            int c = CR(l, last);
            if(c!=-1){
                if(Merge(l, last, c)) all_false = false;
            }
            c = CR(r, last);
            if(c!=-1){
                if(Merge(r, last, c)) all_false = false;
            }
        }
        if(all_false) break;
    }

    for(int i=0;i<N;i++) if(Find(i)==i && child[i].size() > N/2) return i;
    return -1;
}

Compilation message

lokahia.cpp: In function 'int FindBase(int)':
lokahia.cpp:105:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<N;i++) if(Find(i)==i && child[i].size() > N/2) return i;
                                           ~~~~~~~~~~~~~~~~^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 768 KB Correct : C = 250
2 Correct 8 ms 768 KB Correct : C = 231
3 Correct 6 ms 512 KB Correct : C = 3
4 Correct 7 ms 768 KB Correct : C = 231
5 Correct 7 ms 688 KB Correct : C = 60
6 Correct 6 ms 768 KB Correct : C = 224
7 Correct 8 ms 768 KB Correct : C = 300
8 Correct 6 ms 640 KB Correct : C = 167
9 Correct 7 ms 768 KB Correct : C = 297
10 Correct 6 ms 768 KB Correct : C = 101
11 Correct 8 ms 768 KB Correct : C = 300
12 Correct 5 ms 640 KB Correct : C = 180
13 Correct 6 ms 640 KB Correct : C = 128
14 Correct 7 ms 768 KB Correct : C = 100
15 Correct 6 ms 636 KB Correct : C = 192
16 Correct 6 ms 640 KB Correct : C = 61
17 Correct 6 ms 768 KB Correct : C = 100
18 Correct 7 ms 768 KB Correct : C = 271
19 Correct 6 ms 640 KB Correct : C = 60
20 Correct 7 ms 640 KB Correct : C = 60
21 Correct 6 ms 640 KB Correct : C = 165
22 Correct 6 ms 768 KB Correct : C = 266
23 Correct 5 ms 384 KB Correct : C = 0
24 Correct 6 ms 620 KB Correct : C = 158
25 Correct 7 ms 768 KB Correct : C = 100
26 Correct 7 ms 768 KB Correct : C = 300
27 Correct 6 ms 768 KB Correct : C = 300