This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int n;
vector<int> father;
int root(int node){
if(father[node] == node) return node;
return father[node] = root(father[node]);
}
int merge(int NodeA, int NodeB, vector<vector<int>> p){
int rootA = root(NodeA);
int rootB = root(NodeB);
father[rootA] = rootB;
for(int i = 0; i < n; ++i){
if(i == rootA or i == rootB)continue;
if(!(((p[rootA][i]) and (p[rootB][i])) or ((!p[rootA][i]) and (!p[rootB][i])))) return 0;
}
return 1;
}
int construct(vector<vector<int>> p){
n = p[0].size();
father = vector<int>(n);
for(int i = 0; i < n; ++i) {
father[i] = i;
}
for(int i = 0; i < n; ++i){
for(int j = i+1; j < n; ++j){
if(p[i][j]){
int sol = merge(i, j, p);
if(!sol) return 0;
}else{
for(int k = 0; k < n; ++k){
if(k == i or k==j) continue;
if(p[i][k] and p[j][k]) return 0;
}
}
}
}
vector<vector<int>> edges(n, vector<int>(n, 0));
for(int i = 0; i < n; ++i) {
int MyRoot = root(i);
if(MyRoot==i) continue;
edges[MyRoot][i] = edges[i][MyRoot] = 1;
}
build(edges);
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... |