Submission #897233

#TimeUsernameProblemLanguageResultExecution timeMemory
897233aqxaGame (IOI14_game)C++17
0 / 100
2 ms2396 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1505; int a[N][N], cnt[N][N]; int _n; vector<int> e; int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool unite(int x, int y) { x = get(x); y = get(y); if (x == y) return false; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; for (int i = 0; i < _n; ++i) { if (e[i] < 0 && i != x && i != y) { cnt[min(x, i)][max(x, i)] += cnt[min(y, i)][max(y, i)]; } } return true; } void initialize(int n) { _n = n; e = vector<int>(n, -1); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { cnt[i][j] = 1; } } } int hasEdge(int u, int v) { u--; v--; if (u > v) swap(u, v); int cu = get(u), cv = get(v); if (cu == cv) return 1; if (cu > cv) swap(cu, cv); if (cnt[cu][cv] == 1) { unite(cu, cv); // int np = get(cu); // for (int i = 0; i < _n; ++i) { // if (e[i] < 0 && i != cu && i != cv) { // cnt[min(i, np)][max(i, np)] = cnt[min(i, cu)][max(i, cu)] + cnt[min(i, cv)][max(i, cv)]; // } // } return 1; } else { cnt[cu][cv]--; return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...