제출 #379477

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

lokahia

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#include "lokahia.h"
int Q[205][205];
const int LIM = 400;
vector<int> ord;
int tq = 0;
int query(int i, int j){
    if (i == j) return Q[i][i] = i;
    else if (tq >= LIM) return -1;
    else if (Q[i][j] == -2) {
        tq++;
        return Q[i][j] = Q[j][i] = CollectRelics(i,j);
    }
    else return Q[i][j];
}
int c[205];
int p[205];
int rk[205];
int sz[205];
void init(int n){
    for (int i = 0; i < n; i++){
        p[i] = i;
        rk[i] = 0;
        sz[i] = 1;
    }
}
int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}
void un(int x, int y){
    x = find(x) , y= find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) swap(x,y);
    p[y] = x;
    sz[x] += sz[y];
    if (rk[x] == rk[y]) rk[x]++;
}
vector<ii> v;
int FindBase(int N){
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) Q[i][j] = -2;
    init(N);
    ord.resize(N);
    iota(ord.begin(), ord.end(), 0);
    random_shuffle(ord.begin(),ord.end());
    for (int i = 0; i < N/2; i++){
        int Q = query(ord[2*i],ord[2*i+1]);
        if (Q != -1){
            c[Q]+=2;
            un(Q, ord[2*i]);
            un(Q, ord[2*i+1]);
        }
        else{
            c[ord[2*i]]++;
            c[ord[2*i+1]]++;
        }
    }
    for (int i = 0; i < N; i++){
        if (c[i]) v.push_back({c[i],i});
    }
    sort(v.begin(),v.end());
    int st = v[0].second;
    vector<int> good, bad;
    for (auto x : v){
        if (find(x.second) != find(st)) good.push_back(x.second);
    }
    while (good.size() && tq <= LIM){
        sort(good.begin(),good.end());
        srand(time(NULL));
        random_shuffle(good.begin(),good.end());
        for (auto x : good){
            if (st == x) continue;
            int q = query(st,x);
            if (q != -1){
                if (q > st) st = q;
                un(st,q);
            }
            else bad.push_back(x);
        }
        if (sz[find(st)] > N/2) return st;
        vector<int> bad;
        good.clear();
        for (auto x : bad){
            good.push_back(x);
        }
        bad.clear();
    }
    return -1;
}

• Subtask 1: 0 / 100