제출 #168342

#제출 시각아이디문제언어결과실행 시간메모리
168342johutha게임 (IOI14_game)C++14
15 / 100
2 ms424 KiB
#include "game.h" #include <vector> #include <iostream> #include <algorithm> using namespace std; struct unionfind { vector<int> boss; int find(int x) { if (boss[x] == x) return x; return boss[x] = find(boss[x]); } void unite(int a, int b) { if (rand() % 2 == 0) { boss[find(a)] = find(b); } else { boss[find(b)] = find(a); } } void init(int n) { boss.resize(n); for (int i = 0; i < n; i++) { boss[i] = i; } } }; struct graph { int n; vector<vector<int>> conns; unionfind uf; void init(int in) { n = in; uf.init(n); conns.resize(n, vector<int>(n, 1)); } int& conn(int a, int b) { return conns[max(a, b)][min(a, b)]; } void addedge(int a, int b) { vector<int> newvals(n); for (int i = 0; i < n; i++) { newvals[i] = -1; if (uf.find(i) == i && i != a && i != b) { newvals[i] = conn(a, i) + conn(b, i); } } uf.unite(a, b); for (int i = 0; i < n; i++) { if (newvals[i] != -1) { conn(i, uf.find(a)) = newvals[i]; } } } void unadd(int a, int b) { conn(uf.find(a), uf.find(b))--; } bool shouldadd(int a, int b) { return conn(uf.find(a), uf.find(b)) == 1; } }; graph g; void initialize(int n) { g.init(n); } int hasEdge(int u, int v) { if (g.shouldadd(u, v)) { g.addedge(u, v); return 1; } else { g.unadd(u, v); return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...