| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 317675 | tengiz05 | 슈퍼트리 잇기 (IOI20_supertrees) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<int> p, rnk, sz;
void init(int n){
p.assign(n, 0);rnk.assign(n, 0);sz.assign(n, 1);
for(int i=0;i<n;i++)p[i] = i;
}
int par(int i){
if(p[i] == i)return i;
else return p[i] = par(p[i]);
}
bool issame(int i, int j){
return (par(i) == par(j));
}
void merge(int i, int j){
i=par(i), j=par(j);
if(i == j)return;
if(rnk[i] > rnk[j]){
rnk[i]++;sz[i] += sz[j];
p[j] = i;
}else {
rnk[j]++;sz[j] += sz[i];
p[i] = j;
}
}
int setsize(int i){
return sz[par(i)];
}
};
bool is;
vector<bool> vis;
vector<vector<int>> ans;
int node;
void dfs(vector<vector<int>> &p, int u, int par){
vis[u] = true;
for(int v=0;v<n;v++){
if(!ans[u][v])continue;
if(v != par && v == node && p[u][v] == 1){
is = false;
return;
}
if(!vis[v])dfs(p, v, u);
}
}
int construct(vector<vector<int>> p) {
int n = p.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][j] == 3)return 0;
}
}
DSU dsu; dsu.init(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 0 && dsu.issame(i, j))return 0;
else if (p[i][j] > 0){
dsu.merge(i, j);
}
}
}
vector<bool> used(n);
vector<bool> ok(n, true);
ans.assign(n, vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(i != j && p[i][j] == 1)ok[i] = false;
}
}
DSU d; d.init(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 1){
if(d.issame(i, j))continue;
ans[i][j] = 1;
ans[j][i] = 1;
d.merge(i, j);
}
}
if(used[i])continue;
int ind = -1;
for(int j=i+1;j<n;j++){
if(p[i][j] == 2 && !used[j])ind = j;
}
if(ind == -1 || !ok[i])continue;
queue<int> q;q.push(i);used[i] = true;
vector<int> t;
while(!q.empty()){
int u = q.front();q.pop();
t.push_back(u);
for(int v=0;v<n;v++){
if(ok[v] && !used[v] && p[u][v] == 2){
used[v] = true;
q.push(v);
}
}
}//for(auto x : t)cout << x << ' ';cout << '\n';
if(t.size() < 3)return 0;
t.push_back(t[0]);
for(int j=1;j<(int)t.size();j++){
ans[t[j]][t[j-1]] = 1;
ans[t[j-1]][t[j]] = 1;
}
}
for(int i=0;i<n;i++){
if(ok[i])continue;
is = true;
vis.assign(n, 0);
node = i;
dfs(p, i, i);
if(!is)return 0;
}
build(ans);
return 1;
}
/*
5
1 1 2 2 1
1 1 2 2 2
2 2 1 2 2
2 2 2 1 2
1 2 2 2 1
*/