이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "supertrees.h"
#include <vector>
using namespace std;
struct dsu_t{
int n;
int father[1005];
dsu_t(int n){
this->n = n;
for(int i = 0;i < n;i++){
father[i] = -1;
}
}
int find_root(int nod){
if(father[nod] == -1){
return nod;
}
return father[nod] = find_root(father[nod]);
}
bool unite(int x,int y){
x = find_root(x);
y = find_root(y);
if(x == y){
return false;
}
father[x] = y;
return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n,vector<int>(n,0));
dsu_t dsu(n);
for (int i = 0; i < n; i++) {
for(int j = 0;j < n;j++){
if(p[i][j] == 3){
return 0;
}
else if(p[i][j] == 1){
if(dsu.unite(i,j)){
answer[i][j] = answer[j][i] = 1;
}
}
}
}
for (int i = 0; i < n; i++) {
for(int j = 0;j < n;j++){
if(p[i][j] == 2){
if(dsu.find_root(i) == dsu.find_root(j)){
return 0;
}
}
}
}
vector<int> roots;
for(int i = 0;i < n;i++){
if(dsu.find_root(i) == i){
roots.push_back(i);
}
}
if(roots.size() == 2){
return 0;
}
for(int i = 0;i < (int)roots.size();i++){
answer[roots[i]][roots[(i + 1) % roots.size()]] = 1;
answer[roots[(i + 1) % roots.size()]][roots[i]] = 1;
}
build(answer);
return 1;
}
# | 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... |