# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
247248 | 2020-07-11T08:24:11 Z | dwsc | Lokahian Relics (FXCUP4_lokahia) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "lokahia.h" using namespace std; int p[210]; int visit[210][210]; int num[210]; int findset(int i){ return p[i]==i?p[i]:p[i]=findset(p[i]); } int FindBase(int N){ srand(345) int counter = 0; for (int i = 0; i < N; i++) p[i] = i; int fail = 0; while (counter < 600){ int a = rand()%N,b = rand()%N; if (fail > 1000) break; fail++; if (a == b) continue; if (visit[a][b]) continue; if (findset(a) == findset(b)) continue; fail = 0; counter++; visit[a][b] = visit[b][a] = 1; int temp = CollectRelics(a,b); if (temp != -1) { p[findset(a)] = temp; p[findset(b)] = temp; } } for (int i = 0; i < N; i++){ num[findset(i)]++; } for (int i = 0; i < N; i++) if (num[i] > N/2) return i; return -1; }