Submission #930909

#TimeUsernameProblemLanguageResultExecution timeMemory
930909Art_ogoGame (IOI14_game)C++17
100 / 100
261 ms26708 KiB
#include <bits/stdc++.h> #include "game.h" using namespace std; const int MAXN = 1600; int p[MAXN]; int sz[MAXN]; int cnt[MAXN][MAXN]; int find_set(int a){ if(p[a] == a) return a; return p[a] = find_set(p[a]); } void union_sets(int a, int b){ a = find_set(a); b = find_set(b); if(a == b) return; if(sz[a] < sz[b]) swap(a, b); for(int i = 0; i < MAXN; i++){ cnt[i][a] += cnt[b][i]; cnt[a][i] += cnt[b][i]; } p[b] = a; sz[a] += sz[b]; } void initialize(int n) { memset(cnt, 0, sizeof(cnt)); for(int i = 0; i <= n; i++){ p[i] = i; sz[i] = 1; } } int hasEdge(int u, int v) { u = find_set(u); v = find_set(v); if(u == v) return 0; cnt[u][v]++; cnt[v][u]++; if(cnt[u][v] == sz[u]*sz[v]){ union_sets(u, v); return 1; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...