제출 #677608

#제출 시각아이디문제언어결과실행 시간메모리
677608ThegeekKnight16게임 (IOI14_game)C++17
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; vector<set<int> > grafo; vector<map<int, int> > Marc; vector<int> pai; vector<int> prof; int quantF = 2; int N; int find(int v) { if (v == pai[v]) return v; return pai[v] = find(pai[v]); } void une(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (prof[a] < prof[b]) swap(a, b); pai[b] = a; prof[a] = max(prof[a], prof[b] + 1); for (int j = 0; j < N; j++) Marc[a][j] += Marc[b][j]; for (auto x : grafo[b]) grafo[a].insert(find(x)); } void initialize(int n) { grafo.resize(n+1); pai.resize(n+1); prof.resize(n+1); Marc.resize(n+1); N = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) if (i != j) {grafo[i].insert(j); Marc[i][j] = 1;} pai[i] = i; prof[i] = 1; } } int hasEdge(int u, int v) { u = find(u); v = find(v); if (u == v) return 0; // cerr << "PENIS" << '\n'; for (auto x = grafo[u].begin(); x != grafo[u].end();) { if (find(*x) != *x || *x == u) x = grafo[u].erase(x); else x++; } for (auto x = grafo[v].begin(); x != grafo[v].end();) { if (find(*x) != *x || *x == v) x = grafo[v].erase(x); else x++; } /* cerr << u << " " << v << '\n'; cerr << Marc[u][v] << " " << Marc[v][u] << '\n'; cerr << grafo[u].size() << " " << grafo[v].size() << '\n'; */ if (Marc[u][v] == 0 && Marc[v][u] == 0) { Marc[u][v] = Marc[v][u] = 0; grafo[u].erase(v); grafo[v].erase(u); return 0; } else if (Marc[u][v] > 1 && Marc[v][u] > 1) { Marc[u][v]--; Marc[v][u]--; return 0; } else if (grafo[u].size() > 2 && grafo[v].size() > 2) { Marc[u][v]--; Marc[v][u]--; if (Marc[u][v] == 0) grafo[u].erase(v); if (Marc[v][u] == 0) grafo[v].erase(u); return 0; } else if (grafo[u].size() == 2 && grafo[v].size() == 2) { if (quantF == 2) { Marc[u][v]--; Marc[v][u]--; if (Marc[u][v] == 0) {grafo[u].erase(v);} if (Marc[v][u] == 0) {grafo[v].erase(u);} if (grafo[u].size() == 1) quantF--; if (grafo[v].size() == 1) quantF--; return 0; } else { Marc[u][v] = Marc[v][u] = 0; grafo[u].erase(v); grafo[v].erase(u); une(u, v); return 1; } } else if ((grafo[u].size() == 2 || grafo[v].size() == 2)) { if (quantF) { Marc[u][v]--; Marc[v][u]--; if (Marc[u][v] == 0) {grafo[u].erase(v);} if (Marc[v][u] == 0) {grafo[v].erase(u);} if (grafo[u].size() == 1) quantF--; if (grafo[v].size() == 1) quantF--; return 0; } else { Marc[u][v] = Marc[v][u] = 0; grafo[u].erase(v); grafo[v].erase(u); une(u, v); return 1; } } else if (grafo[u].size() == 1 || grafo[v].size() == 1) { Marc[u][v] = Marc[v][u] = 0; grafo[u].erase(v); grafo[v].erase(u); une(u, v); return 1; } else { Marc[u][v]--; Marc[v][u]--; if (Marc[u][v] == 0) grafo[u].erase(v); if (Marc[v][u] == 0) grafo[v].erase(u); return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...