| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 247358 | 2020-07-11T08:57:36 Z | dantoh000 | Lokahian Relics (FXCUP4_lokahia) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
#include "lokahia.h"
int Q[205][205];
const int LIM = 400;
int tq = 0;
int p[205];
int find(int x){
return p[x] == x ? x: p[x] = find(p[x]);
}
int query(int i, int j){
i = find(i), j = find(j);
if (i == j) return Q[i][i] = i;
else if (tq >= LIM) return -1;
else{
for (int x = 0; x < N; x++){
for (int y = 0; y < N; y++){
if (find(x) == i && find(y) == j && Q[x][y] != -2){
return Q[i][j] = Q[j][i] = Q[x][y];
}
}
}
tq++;
return Q[i][j] = Q[j][i] = CollectRelics(i,j);
}
}
int FindBase(int N){
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) Q[i][j] = -2;
p[i] = i;
}
vector<int> good;
for (int i = 0; i < N; i++) good.push_back(i);
while (good.size() && tq <= LIM){
int cur = good[0];
srand(time(NULL));
random_shuffle(good.begin(),good.end());
for (auto x : good){
if (cur == x) continue;
int q = query(cur,x);
if (q != -1 && q > cur) {
p[cur] = p[x] = q;
cur = q;
}
}
int ct = 0;
vector<int> bad;
for (auto x : good){
if (x == cur || query(x,cur) != -1) {
p[x] = cur;
ct++;
}
else bad.push_back(x);
if (ct > N/2) break;
}
if (ct > N/2) return cur;
good.clear();
for (auto x : bad){
good.push_back(x);
}
bad.clear();
}
return -1;
}