| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 738955 | 1ne | 게임 (IOI14_game) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>res;
struct DSU{
vector<int>parent,sz;
DSU(int n){
parent.resize(n);
sz.resize(n,1);
iota(parent.begin(),parent.end(),0);
}
int findsets(int v){
if (v == parent[v]){
return v;
}
parent[v] = findsets(parent[v]);
return parent[v];
}
bool unionset(int u,int v){
u = findsets(u);
v = findsets(v);
if (u == v){
return false;
}
if (sz[v] > sz[u]){
swap(u,v);
}
parent[v] = u;
sz[u]+=sz[v];
return true;
};
};
DSU st(1501);
vector<int>with;
void initialize(int n) {
res.resize(n,n - 1);
with.resize(n,0);
}
int hasEdge(int u, int v) {
if (st.findsets(u) == st.findsets(v)){
res[u]--;
res[v]--;
return 0;
}
if ((res[u] == 1 && res[v] >= 1) || (res[v] == 1 && res[u] >= 1)){
st.unionset(u,v);
res[u]--;
res[v]--;
with[u] = 1;
with[v] = 1;
checked[u][v] = 1;
checked[v][u] = 1;
return 1;
}
res[u]--;
res[v]--;
return 0;
}