이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
int n;
vector<int> parent,sz;
DSU(int _n){
n = _n;
for(int i=0;i<=n;i++){
parent.push_back(i);
sz.push_back(1);
}
}
int find(int x){
return parent[x] = (parent[x] == x ? x : find(parent[x]));
}
void unite(int a,int b){
a = find(a);
b = find(b);
if(a != b){
if(sz[a] >= sz[b]){
parent[b] = a;
sz[a] += sz[b];
}else{
parent[a] = b;
sz[b] += sz[a];
}
}
}
};
int construct_1(vector<vector<int>> p) {
// 21
int n = p.size();
vector<vector<int>> answer(n,vector<int>(n,0));
DSU comp(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] >= 2)return 0;
if(p[i][j] == 1)comp.unite(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
}
}
vector<bool> vis(n,0);
for(int i=0;i<n;i++){
if(vis[i])continue;
vis[i] = 1;
for(int j=0;j<n;j++){
if(vis[j])continue;
if(comp.find(i) == comp.find(j)){
answer[i][j] = answer[j][i] = 1;
vis[j] = 1;
}
}
}
build(answer);
return 1;
}
int construct_2(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n,vector<int>(n,0));
DSU comp(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 3 || p[i][j] == 1)return 0;
if(p[i][j] == 2)comp.unite(i,j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
}
}
vector<bool> vis(n,0);
map<int,vector<int>> comps;
for(int i=0;i<n;i++){
comps[comp.find(i)].push_back(i);
}
for(auto i:comps){
vector<int> &p = i.second;
if((int)p.size() == 2)return 0;
if((int)p.size() < 2)continue;
for(int i=1;i<(int)p.size();i++){
answer[p[i]][p[i-1]] = answer[p[i-1]][p[i]] = 1;
}
answer[p[(int)p.size()-1]][p[0]] = answer[p[0]][p[(int)p.size()-1]] = 1;
}
build(answer);
return 1;
}
int construct_3(vector<vector<int>> p) {
//answer exists
cerr<<"3>>"<<endl;
int n = p.size();
vector<vector<int>> answer(n,vector<int>(n,0));
DSU comp(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 1)comp.unite(i,j);
}
}
vector<bool> vis(n,0);
vector<bool> is_root(n,0);
for(int i=0;i<n;i++){
if(vis[i])continue;
vis[i] = 1;
is_root[i] = 1;
for(int j=0;j<n;j++){
if(vis[j])continue;
if(comp.find(i) == comp.find(j)){
answer[i][j] = answer[j][i] = 1;
vis[j] = 1;
}
}
}
DSU nxt(n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 2)nxt.unite(i,j);
}
}
map<int,vector<int>> comps;
for(int i=0;i<n;i++){
if(is_root[i])comps[nxt.find(i)].push_back(i);
}
for(auto i:comps){
vector<int> &p = i.second;
if((int)p.size() < 2)continue;
for(int i=1;i<(int)p.size();i++){
answer[p[i]][p[i-1]] = answer[p[i-1]][p[i]] = 1;
}
answer[p[(int)p.size()-1]][p[0]] = answer[p[0]][p[(int)p.size()-1]] = 1;
}
build(answer);
return 1;
}
int construct(vector<vector<int>> p) {
int n = p.size();
bool one = 1,two = 1;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(p[i][j] == 2)one = 0;
if(p[i][j] == 1)two = 0;
}
}
if(one)return construct_1(p);
else if(two)return construct_2(p);
return construct_3(p);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |