#include "supertrees.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ld long double
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 200 + 10 , sq = 333 , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 7 ;
int n , ok =1 , cnt2 = 1 , cnt = 1 , mark[maxn] ,p[maxn][maxn] , b[maxn][maxn] , c[maxn] , ye[maxn] , c2[maxn] ;
vector <int> vec ;
void dfs(int v){
vec.pb(v) ;
c[v] = cnt ;
mark[v] =1 ;
rep(j , 0 ,n-1){
if(mark[j]==0 && p[v][j]){
dfs(j) ;
}
}
}
vector <int> vec2 ;
void dfs2(int v){
mark[v] =1 ;
c2[v] = cnt2 ;
ye[cnt2] = v;
for(int u : vec2){
if(mark[u]==1 || p[v][u] == 2)continue ;
dfs2(u) ;
}
}
void add(int x ,int y){
b[x][y] = b[y][x] =1 ;
}
bool ch(vector <int> vec){
vec2 = vec ;
cnt2 = 1 ;
for(int x : vec)mark[x] =0 ;
for(int x : vec){
if(mark[x] == 1)continue ;
dfs2(x) ;
cnt2++ ;
}
cnt2--;
for(int x : vec){
for(int y : vec){
if(c2[x] == c2[y] && p[x][y] == 2)return 0 ;
}
}
rep(i , 1 ,cnt2){
vector <int> az ;
for(int x : vec){
if(c2[x] == i)az.pb(x);
}
rep(j ,1 ,sz(az)-1)add(az[j-1],az[j]) ;
}
if(cnt2 == 2){
if(sz(vec)==2)return 0 ;
vector <int> a[2] ;
for(int v : vec){
a[c2[v]-1].pb(v) ;
}
if(sz(a[0]) > sz(a[1]))swap(a[0] , a[1]) ;
add(a[0][0] , a[1][0]) ;
add(a[0][0] , a[1][1]) ;
return 1 ;
}
add(ye[1],ye[cnt2]) ;
rep(i ,2 , cnt2){
add(ye[i-1] , ye[i]);
}
return 1 ;
}
int construct(vector<std::vector<int>> pp) {
n = sz(pp);
rep(i , 0 , n-1){
rep(j , 0 ,n-1){
p[i][j] = pp[i][j] ;
if(p[i][j] == 3)return 0 ;
}
}
rep(i ,0 , n-1){
if(mark[i] == 1)continue ;
dfs(i) ;
cnt++;
}
cnt--;
rep(i ,0 ,n-1){
rep(j , 0 ,n-1){
if((c[i]==c[j] && p[i][j]==0) || (c[i]!=c[j] && p[i][j]>0))return 0 ;
}
}
rep(i , 1, cnt){
vector <int> vec;
rep(j , 0 , n-1){
if(c[j] == i){
vec.pb(j) ;
}
}
if(ch(vec)==0)return 0 ;
}
vector <vector <int> > bb ;
rep(i , 0 , n-1){
vector <int> f ;
rep(j , 0, n-1){
f.pb(b[i][j]) ;
}
bb.pb(f) ;
}
build(bb) ;
return 1 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
b[0][0] is not 0 |
| 2 |
Halted |
0 ms |
0 KB |
- |
