Submission #677610

#TimeUsernameProblemLanguageResultExecution timeMemory
677610ThegeekKnight16Game (IOI14_game)C++17
42 / 100
1094 ms53732 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; vector<map<int, int> > Marc; vector<int> pai; vector<int> prof; 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]; Marc[j][a] += Marc[j][b];} } void initialize(int n) { 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) {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; if (Marc[u][v] > 1) { Marc[u][v]--; Marc[v][u]--; return 0; } une(u, v); return true; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...