제출 #835141

#제출 시각아이디문제언어결과실행 시간메모리
835141gustason게임 (IOI14_game)C++14
0 / 100
1 ms212 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; constexpr int nax = 81; int N; struct Dsu { int par[nax]; int sz[nax]; Dsu(int n=nax) { for(int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } } int find(int v) { if (par[v] == v) { return v; } return par[v] = find(par[v]); } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) { return false; } if (sz[b] > sz[a]) { swap(a, b); } par[b] = a; sz[a] += sz[b]; return true; } bool form_full() { return sz[find(0)] == N; } }; bool form_full(Dsu a, Dsu& b) { for(int i = 0; i < N; i++) { for(int j = i+1; j < N; j++) { if (b.find(i) == b.find(j)) { a.unite(i, j); } } } return a.form_full(); } Dsu curr; vector<pair<int, int>> edges; void initialize(int n) { N = n; // curr + all Yes -> form full // curr + all No -> not form full for(int i = 0; i < n; i++) { for(int j = i+1; j < n; j++) { edges.emplace_back(i, j); } } } int hasEdge(int u, int v) { if (u > v) { swap(u, v); } edges.erase(find(edges.begin(), edges.end(), pair<int, int>(u, v))); Dsu curr_add = curr; curr_add.unite(u, v); if (curr_add.form_full()) { return 0; } Dsu curr_all = curr_add; for(auto& i : edges) { curr_all.unite(i.first, i.second); } if (!curr_all.form_full()) { return 0; } curr = curr_add; return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...