제출 #150308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
150308		Cafe Maru (#200)	Lokahian Relics (FXCUP4_lokahia)	C++17	51 / 100	8 ms	976 KiB

lokahia

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

컴파일 시 표준 에러 (stderr) 메시지

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: 51 / 100