Submission #288566

#TimeUsernameProblemLanguageResultExecution timeMemory
288566emil_physmathGame (IOI14_game)C++17
42 / 100
1100 ms35576 KiB
#pragma GCC target ("avx2") #pragma GCC optimization ("O2") #pragma GCC optimization ("unroll-loops") #include <unordered_map> #include <iostream> #include <algorithm> #include <vector> #include <map> #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';} int n; int cnt[maxN][maxN]; unordered_map<int, int> nei[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); int c1 = centre[u], c2 = centre[v]; if (nei[c1].size() > nei[c2].size()) swap(c1, c2); for (pair<int, int> to: nei[c1]) { int t = to.first; if (t == c2) continue; nei[t].erase(c1); nei[c2][t] += to.second; nei[t][c2] += to.second; } // nei[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; nei[v].reserve(n); nei[v].reserve(1024); nei[v].max_load_factor(0.25); } } int hasEdge(int u, int v) { int c1 = centre[Root(u)]; int c2 = centre[Root(v)]; int tch = ++nei[c1][c2]; ++nei[c2][c1]; if (tch == sz[Root(u)] * sz[Root(v)]) { Union(u, v); return 1; } return 0; }

Compilation message (stderr)

game.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O2")
      | 
game.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...