제출 #596529

#제출 시각아이디문제언어결과실행 시간메모리
596529Elias게임 (IOI14_game)C++17
0 / 100
0 ms212 KiB
#include <bits/stdc++.h> #ifndef _DEBUG #include "game.h" #endif using namespace std; vector<int> parent; // logn union find vector<set<int>> queried; int n; int find(int a) { if (parent[a] == a) return a; return parent[a] = find(parent[a]); } void initialize(int n) { ::n = n; parent = vector<int>(n); queried = vector<set<int>>(n); for (int i = 0; i < n; i++) { parent[i] = i; } } int hasEdge(int u, int v) { queried[u].insert(v); queried[v].insert(u); int U = find(u); int V = find(v); if (U > V) swap(U, V), swap(u, v); bool a = U == 0; int b = U == 0; if (a ^ b) { for (int i = 0; i < n; i++) // only insert edge if last query to group zero if (find(i) == 0 && !queried[v].count(i)) return 0; parent[V] = 0; assert(U == 0); return 1; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...