| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 558142 | Olympia | Game (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();
vector<int> vec;
for (int i = 0; i < n; i++) {
vec.push_back(i);
}
random_shuffle(vec.begin(), vec.end());
for (int i: vec) {
for (int j: vec) {
if (!d.comp(i, j)) {
d.join(i, j);
edges.insert(make_pair(min(i, j), max(i, j)));
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j) {
e.insert(make_pair(min(i, j), max(i, j)));
}
}
}
}
int hasEdge (int u, int v) {
assert(edges.size() == d.n - 1);
if (!edges.count(make_pair(u, v)) && !edges.count(make_pair(v, u))) {
e.erase(make_pair(min(u, v), max(u, v)));
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);
}
}
assert(d.cc == 2);
for (auto& p: e) {
if (p == make_pair(u, v) || p == make_pair(v, u)) continue;
if (!d.comp(p.first, p.second)) {
edges.erase(make_pair(min(u, v), max(u, v)));
e.erase(make_pair(min(u, v), max(u, v)));
edges.insert(p);
return false;
}
}
return true;
}
int main() {
initialize(4);
cout << hasEdge(0, 1) << '\n';
cout << hasEdge(0, 3) << '\n';
cout << hasEdge(1, 3) << '\n';
cout << hasEdge(1, 2) << '\n';
cout << hasEdge(2, 0) << '\n';
cout << hasEdge(2, 3) << '\n';
}