#include "supertrees.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
bool used[maxn];
vector < int > v[maxn],c;
void dfs( int x )
{
if( used[x] )return;
used[x] = true;
c.push_back(x);
for( auto y : v[x] ){
dfs( y );
}
}
int construct( vector<vector<int>> p )
{
int n = (int)p.size();
for( int i = 0; i < n; i++ ){
if( p[i][i] != 1 )return 0;
for( int j = 0; j < n; j++ ){
if( p[i][j] == 3 || p[i][j] != p[j][i] )return 0;
if( p[i][j] == 0 )continue;
if( p[i][j] == 1 ){
v[i].push_back(j);
}
}
}
vector < vector < int > > ans( n , vector < int > (n , 0) );
vector < int > fg;
vector < vector < int > > gr(n);
for( int it = 0; it < n; it++ ){
if( used[it] )continue;
c.clear();
dfs( it );
fg.push_back(it);
gr[it] = c;
int sz = (int)c.size();
int cnt1 = 0 , cnt2 = 0;
vector < int > ch( n , 0 );
for( int i = 0; i < sz; i++ ){
ch[c[i]] = 1;
for( int j = 0; j < sz; j++ ){
int x = c[i] , y = c[j];
if( p[x][y] != 1 ){
return 0;
}
}
if( i + 1 < sz ){
int x = c[i] , y = c[i + 1];
ans[x][y] = ans[y][x] = 1;
}
}
for( int i = 0; i < sz; i++ ){
for( int j = 0; j < n; j++ ){
int x = c[i] , y = j;
if( ch[y] )continue;
cnt1 += 1;
if( p[x][y] == 0 )cnt2 += 1;
}
}
if( cnt2 == cnt1 ){
fg.pop_back();
}
}
for( int i = 0; i < n; i++ ){
used[i] = false;
v[i].clear();
for( int j = 0; j < n; j++ ){
if( p[i][j] != 0 ){
v[i].push_back(j);
}
}
}
for( int i = 0; i < n; i++ ){
if( used[i] )continue;
c.clear();
dfs( i );
vector < int > g;
for( auto x : c ){
if( !gr[x].empty() ){
g.push_back(x);
}
}
for( int j = 0; j < (int)g.size(); j++ ){
for( auto x : gr[g[j]] ){
for( int h = 0; h < (int)g.size(); h++ ){
if( j == h )continue;
for( auto y : gr[g[h]] ){
if( p[x][y] == 1 ){
return 0;
}
}
}
}
}
for( int j = 0; j + 1 < (int)g.size(); j++ ){
int x = g[j] , y = g[j + 1];
ans[x][y] = ans[y][x] = 1;
}
if( !g.empty() && (int)g.size() < 3 ){
return 0;
}
int x = g[0] , y = g.back();
ans[x][y] = ans[y][x] = 1;
int sz = (int)c.size();
for( int j = 0; j < sz; j++ ){
for( int h = 0; h < sz; h++ ){
int x = c[j] , y = c[h];
if( p[x][y] == 0 ){
return 0;
}
}
}
}
build( ans );
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
288 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
