Submission #1041139

#TimeUsernameProblemLanguageResultExecution timeMemory
1041139vaneaGame (IOI14_game)C++14
100 / 100
244 ms21188 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; using ll = long long; const int mxN = 2e3+10; int p[mxN], n, d[mxN][mxN]; set<int> comp; int get(int x) { return p[x] < 0 ? x : p[x] = get(p[x]); } void uni(int x, int y) { x = get(x); y = get(y); if(p[x] > p[y]) swap(x, y); comp.erase(y); for(auto it : comp) { if(it == x) continue; d[it][x] = d[x][it] = d[x][it] + d[y][it]; } p[x] += p[y]; p[y] = x; } int hasEdge(int x, int y) { if(d[get(x)][get(y)] == 1) { uni(x, y); return 1; } --d[get(x)][get(y)]; --d[get(y)][get(x)]; return 0; } void initialize(int N) { n = N; for(int i = 0; i < n; i++) p[i] = -1; for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { d[i][j] = d[j][i] = 1; } comp.insert(i); } } /* int main() { initialize(4); cout << hasEdge(0, 1) << hasEdge(3, 0) << hasEdge(1, 2) << hasEdge(0, 2); cout << hasEdge(3, 1) << hasEdge(2, 3); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...