Submission #950675

#TimeUsernameProblemLanguageResultExecution timeMemory
950675kilkuwuGame (IOI14_game)C++17
0 / 100
1 ms2396 KiB
#ifdef LOCAL #ifndef _GAME_H #define _GAME_H void initialize(int n); int hasEdge(int u, int v); #include <cstdio> #include <cassert> #include "game.h" int read_int() { int x; assert(scanf("%d", &x) == 1); return x; } int main() { int n, u, v; n = read_int(); initialize(n); for (int i = 0; i < n * (n - 1) / 2; i++) { u = read_int(); v = read_int(); printf("%d\n", hasEdge(u, v)); } return 0; } #endif #else #include "game.h" #endif #include <bits/stdc++.h> struct DSU { std::vector<int> e; int cnt = 0; DSU(int n) : e(n, -1) {} int find(int u) { return e[u] < 0 ? u : e[u] = find(e[u]); } bool merge(int u, int v) { u = find(u), v = find(v); if (u == v) return false; cnt++; if (e[u] > e[v]) std::swap(u, v); e[u] += e[v]; e[v] = u; return true; } bool same(int u, int v) { return find(u) == find(v); } int size(int u) { return -e[find(u)]; } int size() { return e.size() - cnt; } }; const int mxN = 1500; int broken[mxN][mxN]; int n; void initialize(int n) { } int hasEdge(int u, int v) { // let's delete this broken[u][v] = 1; broken[v][u] = 1; DSU dsu(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (!broken[i][j]) { dsu.merge(i, j); } } } if (dsu.size() == 1) { // we can return 0; } else { broken[u][v] = broken[v][u] = 0; return 1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...