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 "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int NAX = 1002;
vector<int> parent(NAX, -1), parent2(NAX, -1);
vector<vector<int> > answer;
vector<vector<int> > P(NAX, vector<int>(NAX));
vector<vector<int> > gsetone(NAX), adj(NAX);
int n;
int Find(int u){
if (parent[u] == -1) return u;
return parent[u] = Find(parent[u]);
}
int Find2(int u){
if (parent2[u] == -1) return u;
return parent2[u] = Find2(parent2[u]);
}
int construct(vector<vector<int> > p) {
n = p.size();
for (int i=0; i<n; i++){
vector<int> row(n);
answer.push_back(row);
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
P[i][j] = p[i][j];
}
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
if (P[i][j] == 1){ // first do the bamboos
int x = Find(i), y = Find(j);
if (x != y){
parent[x] = y;
}
}
}
}
for (int i=0; i<n; i++){
int pp = Find(i);
if (pp != i) gsetone[pp].push_back(i);
}
for (int i=0; i<n; i++){
int u = i;
for (int j=0; j<gsetone[i].size(); j++){
int v = gsetone[i][j];
answer[u][v] = answer[v][u] = 1;
u = v;
}
}
// do the twos
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (i==j) continue;
if (P[i][j] == 2){
int x = Find(i), y = Find(j);
int X = Find2(x), Y = Find2(y);
if (X != Y){
parent2[X] = Y;
}
}
}
}
for (int i=0; i<n; i++){
int pp = Find(i);
int PP = Find2(pp);
if (PP != i){
adj[PP].push_back(i);
}
}
for (int i=0; i<n; i++){
if ((int)adj[i].size() == 1) return 0;
int u = i;
for (int j=0; j<adj[i].size(); j++){
int v = adj[i][j];
answer[u][v] = answer[v][u] = 1;
u = v;
}
if ((int)adj[i].size() > 1) answer[u][i] = answer[i][u] = 1;
}
// check everything:
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
int x = Find(i), y = Find(j);
int X = Find2(x), Y = Find2(y);
if (P[i][j] == 0){
if (X == Y) return 0;
}else if (P[i][j] == 1){
if (x != y) return 0;
}else{
if (x == y || X != Y) return 0;
}
}
}
build(answer);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int j=0; j<gsetone[i].size(); j++){
| ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j=0; j<adj[i].size(); j++){
| ~^~~~~~~~~~~~~~
# | 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... |