#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
int root[1020] , de[1020] , use[1020] , r[1020];
ll find(int u){
if(root[u] == u) return u;
return root[u] = find(root[u]);
}
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> answer(n , vector<int>(n , 0));
for(int i = 0 ; i < n ; ++i){
if(p[i][i] != 1) return 0 ;
root[i] = i ;
}
for(int i = 0 ; i < n; ++i)
for(int j = 0 ; j < n; ++j){
if(!p[i][j]) continue ;
if(p[i][j] == 2 || p[i][j] == 0) r[i]++ ;
root[find(i)] = find(j);
}
for(int i = 0 ; i < n ; ++i) {
if(r[i] == n - 1) de[i] = 1;
else de[i] = 0 ;
find(i);
}
set<int> s[1020][3];
for(int i = 0 ; i < n; ++i)
for(int j = i + 1 ; j < n; ++j){
if(p[i][j] == 0 && root[i] == root[j]) return 0 ;
else if(p[i][j]){
s[root[i]][de[i]].insert(i);
s[root[i]][de[j]].insert(j);
}
}
for(int i = 0 ; i < n; ++i){
if(use[root[i]]) continue;
use[root[i]] = 1;
int ls = -1;
if(!s[root[i]][1].size()){
return 0 ;
for(auto j : s[root[i]][0]){
if(ls != -1){
answer[ls][j] = 1;answer[j][ls] = 1;
}else ls = j ;
}
}else if(!s[root[i]][0].size()){
if(s[root[i]][1].size() <= 2) return 0;
auto it = s[root[i]][1].begin();
auto it1 = s[root[i]][1].begin(); it1++;
auto it2 = s[root[i]][1].begin(); it2++;it2++;
answer[*it][*it1] = 1;answer[*it1][*it] = 1;
for(; it2 != s[root[i]][1].end(); it2++ , it1++){
answer[*it2][*it1] = 1;answer[*it1][*it2] = 1;
}
answer[*it][*it1] = 1;answer[*it1][*it] = 1;
}else{
return 0 ;
if(s[root[i]][1].size() <= 1) return 0;
for(auto j : s[root[i]][0]){
if(ls != -1){
answer[ls][j] = 1;answer[j][ls] = 1;
}else ls = j ;
}
int it = ls;
auto it1 = s[root[i]][1].begin();
auto it2 = s[root[i]][1].begin(); it2++;
answer[it][*it1] = 1;answer[*it1][it] = 1;
for(; it2 != s[root[i]][1].end(); it2++ , it1++){
answer[*it2][*it1] = 1;answer[*it1][*it2] = 1;
}
answer[it][*it1] = 1;answer[*it1][it] = 1;
}
}
build(answer);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 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 |
512 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 |
512 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 |
512 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 |
512 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 |
512 KB |
Answer gives possible 0 while actual possible 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
