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 <iostream>
#include <vector>
#include "supertrees.h"
using namespace std;
const int NN = 1005;
vector<int> nei[NN];
int seen[NN], dfsd[NN];
int d[NN][NN], lab[NN];
void dfs(int u, int r){
dfsd[u] = 1;
d[r][u]++;
for (int i : nei[u])
if (!dfsd[i])
dfs(i, r);
dfsd[u] = 0;
}
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> ans(n, vector<int> (n, 0)), comp, comp2;
vector<int> out;
int z = 0, o = 0, t = 0, th = 0;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++){
z += p[i][j] == 0;
o += p[i][j] == 1;
t += p[i][j] == 2;
th += p[i][j] == 3;
}
if (o and z + t + th == 0){
for (int i=1;i<n;i++)
ans[i-1][i] = ans[i][i-1] = 1;
build(ans);
return 1;
}
if (t + th == 0){
for (int i=0;i<n;i++){
int mx = 0, ind = -1;
for (int k=0;k<comp.size();k++){
int cnt = 0;
for (int j : comp[k])
cnt += p[i][j];
if (cnt == 0)
continue;
if (mx > 0 or cnt != comp[k].size())
return 0;
ind = k;
mx = cnt;
}
if (ind == -1)
comp.push_back({i});
else
comp[ind].push_back(i);
}
for (auto v : comp)
for (int j=1;j<v.size();j++)
ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
build(ans);
return 1;
}
if (o == n and th == 0){
for (int i=0;i<n;i++){
int mx = 0, ind = -1;
for (int k=0;k<comp.size();k++){
int cnt = 0;
for (int j : comp[k])
cnt += p[i][j] == 2;
if (cnt == 0)
continue;
if (mx > 0 or cnt != comp[k].size())
return 0;
ind = k;
mx = cnt;
}
if (ind == -1)
comp.push_back({i});
else
comp[ind].push_back(i);
}
for (auto v : comp){
for (int j=1;j<v.size();j++)
ans[v[j-1]][v[j]] = ans[v[j]][v[j-1]] = 1;
if (v.size() > 1)
ans[v.back()][v[0]] = ans[v[0]][v.back()] = 1;
if (v.size() == 2)
return 0;
}
build(ans);
return 1;
}
if (th)
return 0;
for (int i=0;i<n;i++){
lab[i] = i;
int mx = 0, ind = -1;
for (int k=0;k<comp.size();k++){
int cnt = 0;
for (int j : comp[k])
cnt += p[i][j] == 1;
if (cnt == 0)
continue;
if (cnt == comp[k].size())
ind = k;
}
if (ind == -1)
comp.push_back({i});
else
comp[ind].push_back(i);
}
for (auto v : comp)
for (int j=1;j<v.size();j++)
ans[v[j]][v[j-1]] = ans[v[j-1]][v[j]] = 1, lab[v[j]] = v[0];
comp.clear();
for (int i=0;i<n;i++){
if (seen[lab[i]])
continue;
int ind = -1;
for (int k=0;k<comp.size();k++){
int cnt = 0;
for (int j : comp[k])
cnt += p[i][j] == 2;
if (cnt == 0)
continue;
if (cnt == comp[k].size())
ind = k;
}
seen[lab[i]] = 1;
if (ind == -1)
comp.push_back({i});
else
comp[ind].push_back(i);
}
for (auto v : comp){
if (v.size() == 2)
return 0;
for (int i=1;i<v.size();i++)
ans[v[i]][v[i-1]] = ans[v[i-1]][v[i]] = 1;
ans[v[0]][v.back()] = ans[v.back()][v[0]] = 1;
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (ans[i][j])
nei[i].push_back(j);
for (int i=0;i<n;i++)
dfs(i, i);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (d[i][j] != p[i][j])
return 0;
build(ans);
return 1;
}
Compilation message (stderr)
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:46:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int k=0;k<comp.size();k++){
| ~^~~~~~~~~~~~
supertrees.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (mx > 0 or cnt != comp[k].size())
| ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int j=1;j<v.size();j++)
| ~^~~~~~~~~
supertrees.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int k=0;k<comp.size();k++){
| ~^~~~~~~~~~~~
supertrees.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if (mx > 0 or cnt != comp[k].size())
| ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j=1;j<v.size();j++)
| ~^~~~~~~~~
supertrees.cpp:107:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int k=0;k<comp.size();k++){
| ~^~~~~~~~~~~~
supertrees.cpp:113:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if (cnt == comp[k].size())
| ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:106:7: warning: unused variable 'mx' [-Wunused-variable]
106 | int mx = 0, ind = -1;
| ^~
supertrees.cpp:122:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int j=1;j<v.size();j++)
| ~^~~~~~~~~
supertrees.cpp:131:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for (int k=0;k<comp.size();k++){
| ~^~~~~~~~~~~~
supertrees.cpp:137:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if (cnt == comp[k].size())
| ~~~~^~~~~~~~~~~~~~~~~
supertrees.cpp:150:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int i=1;i<v.size();i++)
| ~^~~~~~~~~
# | 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... |