| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 558134 | Olympia | 게임 (IOI14_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include <game.h>
using namespace std;
struct dsu {
vector<int> parent;
vector<int> compSize;
int n;
int cc;
void fill(){
cc = n;
parent.resize(n), compSize.resize(n);
for(int i = 0; i < n; i++){
parent[i] = i, compSize[i] = 1;
}
}
int find_head(int x){
if(x == parent[x]){
return x;
}
return find_head(parent[x]);
}
void join(int x, int y){
x = find_head(x);
y = find_head(y);
if(x == y){
return;
}
cc--;
if(compSize[x] > compSize[y]){
swap(x,y);
}
parent[x] = y;
compSize[y] += compSize[x];
}
bool comp(int x, int y){
return (find_head(x) == find_head(y));
}
};
set<pair<int,int> > edges;
set<pair<int,int> > e;
dsu d;
void initialize (int n) {
d.n = n;
d.fill();
while (d.cc != 1) {
int u = rand() % n;
int v = rand() % n;
if (!d.comp(u, v)) {
edges.insert(make_pair(u, v));
d.join(u, v);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
e.insert(make_pair(i, j));
}
}
}
}
int hasEdge (int u, int v) {
if (!edges.count(make_pair(u, v)) && !edges.count(make_pair(v, u))) {
e.erase(make_pair(u, v));
e.erase(make_pair(v, u));
return false;
}
d.fill();
for (auto& p: edges) {
if (p != make_pair(u, v) && p != make_pair(v, u)) {
d.join(p.first, p.second);
}
}
for (auto& p: e) {
if (!d.comp(p.first, p.second)) {
edges.erase(make_pair(u, v));
e.erase(make_pair(u, v));
e.erase(make_pair(v, u));
edges.insert(p);
return false;
}
}
return true;
}
int main() {
initialize(4);
cout << hasEdge(0, 1) << '\n';
cout << hasEdge(1, 3) << '\n';
cout << hasEdge(1, 2) << '\n';
cout << hasEdge(2, 0) << '\n';
cout << hasEdge(2, 3) << '\n';
cout << hasEdge(0, 3) << '\n';
}