제출 #288606

#제출 시각아이디문제언어결과실행 시간메모리
288606emil_physmath게임 (IOI14_game)C++17
0 / 100
41 ms36600 KiB
#include <unordered_set> #include <list> #include <random> #include <chrono> #include <iostream> #include <algorithm> #include <vector> #include "game.h" using namespace std; const int maxN = 1500; #define BUGO(x) cerr << #x << " = " << (x) << '\n'; #define BUGOARR(a) {cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } struct custom_hash { int operator()(int x) const { static const int FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return (x + FIXED_RANDOM); } }; struct Set { list<int>::iterator itOf[maxN]; list<int> a; Set() { for (int x = 0; x < maxN; ++x) itOf[x] = a.end(); } void insert(int x) { if (itOf[x] == a.end()) { a.push_back(x); itOf[x] = prev(a.end()); } } void erase(int x) { a.erase(itOf[x]); itOf[x] = a.end(); } int size() { return a.size(); } void clear() { a.clear(); } list<int>::iterator begin() { return a.begin(); } list<int>::iterator end() { return a.end(); } }; int n; Set jmp[maxN]; int nei[maxN][maxN]; int par[maxN], sz[maxN], centre[maxN]; int Root(int v) { return v == par[v] ? v : par[v] = Root(par[v]); } void Union(int u, int v) { u = Root(u); v = Root(v); if (u == v) return; if (sz[u] > sz[v]) swap(u, v); if (rnd(0, 69) <= 5) swap(u, v); int c1 = centre[u], c2 = centre[v]; if (jmp[c1].size() > jmp[c2].size()) swap(c1, c2); for (int t: jmp[c1]) { if (t == c2) continue; nei[t][c1] = 0; jmp[t].erase(c1); nei[c2][t] += nei[c1][t]; nei[t][c2] += nei[c1][t]; jmp[t].insert(c2); jmp[c2].insert(t); } jmp[c1].clear(); sz[v] += sz[u]; par[u] = v; centre[v] = c2; } void initialize(int n_) { n = n_; for (int v = 0; v < n; ++v) par[v] = v, sz[v] = 1, centre[v] = v; } int hasEdge(int u, int v) { int c1 = centre[Root(u)]; int c2 = centre[Root(v)]; jmp[c1].insert(c2); jmp[c2].insert(c1); ++nei[c1][c2]; ++nei[c2][c1]; if (nei[c1][c2] == sz[Root(u)] * sz[Root(v)]) { Union(u, v); return 1; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...