#include "supertrees.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e3+10;
vector<vector<int> > ans;
vector <int> v[MAXN], ones, ch, comp[MAXN];
int par[MAXN], d[MAXN];
bool used[MAXN], fl;
int root(int x) {
if (x==par[x]) return x;
return par[x]=root(par[x]);
}
void connect(int a, int b) {
int ra, rb;
ra=root(a);
rb=root(b);
if (ra==rb) return;
if (d[ra]>d[rb]) par[rb]=ra;
else if (d[rb]>d[ra]) par[ra]=rb;
else {
par[rb]=ra;
d[ra]++;
}
}
void find_comp(int x) {
used[x]=true;
ch.push_back(x);
for (auto i:v[x]) {
if (used[i]) continue;
find_comp(i);
}
}
void add_edge(int a, int b) {
ans[a][b]=ans[b][a]=1;
}
int construct(vector<vector<int> > p) {
int n = p.size();
ans.resize(n);
fl=true;
for (int i=0;i<n;i++) {
if (p[i][i]!=1) fl=false;
for (int j=i+1;j<n;j++) {
if (p[i][j]==3) fl=false;
if (p[i][j]) {
v[i].push_back(j);
v[j].push_back(i);
}
}
par[i]=i;
d[i]=used[i]=0;
ans[i].resize(n);
for (int j=0;j<n;j++) ans[i][j]=0;
}
if (!fl) return 0;
for (int x=0;x<n;x++) {
if (used[x]) continue;
if (!ch.empty()) ch.clear();
find_comp(x);
if (ch.size()==1) continue;
for (int i=0;i<ch.size();i++) {
for (int j=i+1;j<ch.size();j++) {
if (p[ch[i]][ch[j]]==0) fl=false;
else if (p[ch[i]][ch[j]]==1) connect(ch[i],ch[j]);
}
}
if (!ones.empty()) ones.clear();
for (int i=0;i<ch.size();i++) {
int ri=root(ch[i]);
if (comp[ri].empty()) ones.push_back(ri);
comp[ri].push_back(ch[i]);
}
for (int i=0;i<ones.size();i++) {
int nxt=(i-1+ones.size())%ones.size();
add_edge(ones[i],ones[nxt]);
int cur=ones[i];
for (int j=0;j<comp[cur].size();j++) {
if (j>0) add_edge(comp[cur][j-1],comp[cur][j]);
for (int k=1;k<comp[cur].size();k++) {
if (p[comp[cur][j]][comp[cur][j]]==2) fl=false;
}
}
}
}
if (!fl) return 0;
build(ans);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i=0;i<ch.size();i++) {
| ~^~~~~~~~~~
supertrees.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int j=i+1;j<ch.size();j++) {
| ~^~~~~~~~~~
supertrees.cpp:68:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int i=0;i<ch.size();i++) {
| ~^~~~~~~~~~
supertrees.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i=0;i<ones.size();i++) {
| ~^~~~~~~~~~~~
supertrees.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j=0;j<comp[cur].size();j++) {
| ~^~~~~~~~~~~~~~~~~
supertrees.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int k=1;k<comp[cur].size();k++) {
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 1 while actual possible 0 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
b[1][1] is not 0 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
