| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 379474 | dantoh000 | 로카히아 유적 (FXCUP4_lokahia) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#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;
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;
}