| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116965 | Sorting | 늑대인간 (IOI18_werewolf) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
const int LOGN = 20;
vector<int> adj[MAXN], ans;
vector<int> U[MAXN], V[MAXN];
struct dsu{
int par[MAXN], cnt[MAXN];
dsu(){}
dsu(int N){
for(int i = 0; i < N; i++){
par[i] = i;
cnt[i] = 1;
}
}
void find_par(int u){
if(u == par[u]){
return;
}
find_par(u);
par[u] = par[par[u]];
}
bool unite(int u, int v){
find_par(u);
find_par(v);
if(par[u] == par[v]){
return false;
}
if(cnt[par[u]] < cnt[par[v]]){
swap(u, v);
}
cnt[par[u]] += cnt[par[v]];
par[par[v]] = par[u];
return true;
}
};
dsu du, dv;
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R){
for(int i = 0; i < X.size(); i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
n = N;
du = dsu(N);
dv = dsu(N);
for(int i = 0; i < N; i++){
for(int to: adj[i]){
if(du.unite(i, to)){
U[i].push_back(to);
U[to].push_back(i);
}
}
}
for(int i = N - 1; i >= 0; i--){
for(int to: adj[i]){
if(dv.unite(i, to)){
V[i].push_back(to);
V[to].push_back(i);
}
}
}
}
/*vector<int> xv, yv, sv, ev, lv, rv;
int main(){
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
xv.push_back(x);
yv.push_back(y);
}
int q;
cin >> q;
for(int i = 0; i < q; i++){
int sx, ex, lx, rx;
cin >> sx >> ex >> lx >> rx;
sv.push_back(sx);
ev.push_back(ex);
lv.push_back(lx);
rv.push_back(rx);
}
vector<int> res = check_validity(n, xv, yv, sv, ev, lv, rv);
for(int t: res){
cout << t << " ";
}
cout << endl;
return 0;
}*/
/*
2 1
0 1
2
0 1 1 1
1 0 1 2
*/