Submission #693798

#TimeUsernameProblemLanguageResultExecution timeMemory
693798T0p_Game (IOI14_game)C++14
0 / 100
1 ms340 KiB
#include "game.h" #include <bits/stdc++.h> using namespace std; int n; int pa[1500], sz[1500]; bool Asked[1500][1500]; vector<int> g[1500]; int fp(int u) { return pa[u] = (u == pa[u]) ? u : fp(pa[u]); } void initialize(int N) { n = N; for (int i=0 ; i<n ; i++) { pa[i] = i; sz[i] = 1; } } int hasEdge(int u, int v) { Asked[u][v] = Asked[v][u] = true; int uu = fp(u), vv = fp(v); if (uu == vv) return 0; int cntAsked = 0; stack<int> s1; s1.push(uu); while (!s1.empty()) { int u = s1.top(); s1.pop(); stack<int> s2; s2.push(vv); while (!s2.empty()) { int v = s2.top(); s2.pop(); if (Asked[u][v]) cntAsked += 1; for (int x : g[v]) s2.push(x); } for (int x : g[u]) s1.push(x); } if (cntAsked != sz[uu] * sz[vv]) return 0; pa[vv] = uu; sz[uu] += sz[vv]; return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...