#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
#define C continue
typedef vector < int > vi ;
typedef vector < vi > vivi ;
#include "supertrees.h"
int N ;
vi v [1009] , xxx [1009] , comp ;
int col [1009] , P [1009] , who [1009] , timer ;
void dfs ( int node ) {
if ( col [node] ) return ;
col [node] = timer ;
comp .pb ( node ) ;
for ( auto u : v [node] ) dfs ( u ) ;
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
N = n ;
vivi ans ;
for ( int i = 0 ; i < n ; i ++ ) {
vi ret ( n , 0 ) ;
ans .pb ( ret ) ;
}
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < n ; j ++ ) {
if ( p [i][j] == 3 ) return 0 ;
if ( p [i][j] == 1 ) {
v [i] .pb ( j ) ;
}
}
}
for ( int i = 0 ; i < n ; i ++ ) {
if ( col [i] ) C ;
timer ++ ;
comp .clear () ;
dfs ( i ) ;
xxx [timer] = comp ;
P [timer] = comp [0] ;
if ( comp .size () == 1 ) C ;
for ( int j = 0 ; j < ( int ) comp .size () - 1 ; j ++ ) {
int a = comp [j] , b = comp [j+1] ;
ans [a][b] = ans [b][a] = 1 ;
}
for ( auto x : comp ) {
for ( auto y : comp ) {
if ( p [x][y] != 1 ) return 0 ;
}
}
}
timer = 0 ;
for ( int i = 0 ; i < n ; i ++ ) {
who [i] = col [i] ;
v [i] .clear () ;
}
for ( int i = 0 ; i < n ; i ++ ) {
for ( int j = 0 ; j < n ; j ++ ) {
if ( col [i] != col [j] && p [i][j] == 2 ) {
v [P[col[i]]] .pb (P[col[j]]) ;
}
}
}
memset ( col , 0 , sizeof ( col ) ) ;
for ( int i = 0 ; i < n ; i ++ ) {
if ( col [i] ) C ;
timer ++ ;
comp .clear () ;
dfs ( i ) ;
if ( comp .size () == 1 ) C ;
if ( comp .size () == 2 ) return 0 ;
for ( int j = 0 ; j < ( int ) comp .size () - 1 ; j ++ ) {
int a = comp [j] , b = comp [j+1] ;
ans [a][b] = ans [b][a] = 1 ;
}
int a = comp [0] , b = comp .back () ;
ans [a][b] = ans [b][a] = 1 ;
for ( auto x : comp ) {
for ( auto y : comp ) {
if ( x == y ) C ;
for ( auto it1 : xxx [who[x]] ) {
for ( auto it2 : xxx [who[y]] ) {
if ( p [it1][it2] != 2 ) return 0 ;
}
}
}
}
}
build ( ans ) ;
return 1 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1536 KB |
Output is correct |
7 |
Correct |
256 ms |
26232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1536 KB |
Output is correct |
7 |
Correct |
256 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
239 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
1024 KB |
Output is correct |
17 |
Correct |
122 ms |
14840 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5884 KB |
Output is correct |
21 |
Correct |
244 ms |
22776 KB |
Output is correct |
22 |
Correct |
233 ms |
22136 KB |
Output is correct |
23 |
Correct |
260 ms |
24184 KB |
Output is correct |
24 |
Correct |
234 ms |
22264 KB |
Output is correct |
25 |
Correct |
102 ms |
12924 KB |
Output is correct |
26 |
Correct |
98 ms |
12284 KB |
Output is correct |
27 |
Correct |
268 ms |
25208 KB |
Output is correct |
28 |
Correct |
233 ms |
22264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
10 ms |
1280 KB |
Output is correct |
9 |
Correct |
238 ms |
22396 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
12 ms |
1536 KB |
Output is correct |
13 |
Correct |
269 ms |
26360 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
6 ms |
1024 KB |
Output is correct |
17 |
Correct |
131 ms |
14840 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
384 KB |
Output is correct |
21 |
Correct |
60 ms |
5880 KB |
Output is correct |
22 |
Correct |
249 ms |
22776 KB |
Output is correct |
23 |
Correct |
233 ms |
22264 KB |
Output is correct |
24 |
Correct |
275 ms |
25464 KB |
Output is correct |
25 |
Correct |
98 ms |
12312 KB |
Output is correct |
26 |
Correct |
104 ms |
12940 KB |
Output is correct |
27 |
Correct |
243 ms |
22264 KB |
Output is correct |
28 |
Correct |
260 ms |
24184 KB |
Output is correct |
29 |
Correct |
101 ms |
12408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
62 ms |
5880 KB |
Output is correct |
5 |
Correct |
254 ms |
22904 KB |
Output is correct |
6 |
Correct |
233 ms |
22136 KB |
Output is correct |
7 |
Correct |
258 ms |
24184 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
65 ms |
6008 KB |
Output is correct |
10 |
Correct |
245 ms |
22648 KB |
Output is correct |
11 |
Correct |
237 ms |
22264 KB |
Output is correct |
12 |
Correct |
260 ms |
25208 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
60 ms |
5880 KB |
Output is correct |
17 |
Correct |
249 ms |
22776 KB |
Output is correct |
18 |
Correct |
240 ms |
22904 KB |
Output is correct |
19 |
Correct |
243 ms |
22392 KB |
Output is correct |
20 |
Correct |
243 ms |
22416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1536 KB |
Output is correct |
7 |
Correct |
256 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
239 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
1024 KB |
Output is correct |
17 |
Correct |
122 ms |
14840 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5884 KB |
Output is correct |
21 |
Correct |
244 ms |
22776 KB |
Output is correct |
22 |
Correct |
233 ms |
22136 KB |
Output is correct |
23 |
Correct |
260 ms |
24184 KB |
Output is correct |
24 |
Correct |
234 ms |
22264 KB |
Output is correct |
25 |
Correct |
102 ms |
12924 KB |
Output is correct |
26 |
Correct |
98 ms |
12284 KB |
Output is correct |
27 |
Correct |
268 ms |
25208 KB |
Output is correct |
28 |
Correct |
233 ms |
22264 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
238 ms |
22396 KB |
Output is correct |
38 |
Correct |
1 ms |
512 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
12 ms |
1536 KB |
Output is correct |
41 |
Correct |
269 ms |
26360 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
1 ms |
384 KB |
Output is correct |
44 |
Correct |
6 ms |
1024 KB |
Output is correct |
45 |
Correct |
131 ms |
14840 KB |
Output is correct |
46 |
Correct |
1 ms |
512 KB |
Output is correct |
47 |
Correct |
1 ms |
384 KB |
Output is correct |
48 |
Correct |
1 ms |
384 KB |
Output is correct |
49 |
Correct |
60 ms |
5880 KB |
Output is correct |
50 |
Correct |
249 ms |
22776 KB |
Output is correct |
51 |
Correct |
233 ms |
22264 KB |
Output is correct |
52 |
Correct |
275 ms |
25464 KB |
Output is correct |
53 |
Correct |
98 ms |
12312 KB |
Output is correct |
54 |
Correct |
104 ms |
12940 KB |
Output is correct |
55 |
Correct |
243 ms |
22264 KB |
Output is correct |
56 |
Correct |
260 ms |
24184 KB |
Output is correct |
57 |
Correct |
101 ms |
12408 KB |
Output is correct |
58 |
Correct |
1 ms |
512 KB |
Output is correct |
59 |
Correct |
1 ms |
384 KB |
Output is correct |
60 |
Correct |
5 ms |
896 KB |
Output is correct |
61 |
Correct |
118 ms |
14328 KB |
Output is correct |
62 |
Correct |
1 ms |
384 KB |
Output is correct |
63 |
Correct |
1 ms |
384 KB |
Output is correct |
64 |
Correct |
1 ms |
384 KB |
Output is correct |
65 |
Correct |
60 ms |
5880 KB |
Output is correct |
66 |
Correct |
103 ms |
12792 KB |
Output is correct |
67 |
Correct |
99 ms |
12280 KB |
Output is correct |
68 |
Correct |
101 ms |
12536 KB |
Output is correct |
69 |
Correct |
98 ms |
12280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
12 ms |
1536 KB |
Output is correct |
7 |
Correct |
256 ms |
26232 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
384 KB |
Output is correct |
12 |
Correct |
10 ms |
1280 KB |
Output is correct |
13 |
Correct |
239 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
384 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
1024 KB |
Output is correct |
17 |
Correct |
122 ms |
14840 KB |
Output is correct |
18 |
Correct |
1 ms |
512 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
60 ms |
5884 KB |
Output is correct |
21 |
Correct |
244 ms |
22776 KB |
Output is correct |
22 |
Correct |
233 ms |
22136 KB |
Output is correct |
23 |
Correct |
260 ms |
24184 KB |
Output is correct |
24 |
Correct |
234 ms |
22264 KB |
Output is correct |
25 |
Correct |
102 ms |
12924 KB |
Output is correct |
26 |
Correct |
98 ms |
12284 KB |
Output is correct |
27 |
Correct |
268 ms |
25208 KB |
Output is correct |
28 |
Correct |
233 ms |
22264 KB |
Output is correct |
29 |
Correct |
1 ms |
384 KB |
Output is correct |
30 |
Correct |
1 ms |
384 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
1 ms |
384 KB |
Output is correct |
33 |
Correct |
1 ms |
384 KB |
Output is correct |
34 |
Correct |
1 ms |
384 KB |
Output is correct |
35 |
Correct |
1 ms |
384 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
238 ms |
22396 KB |
Output is correct |
38 |
Correct |
1 ms |
512 KB |
Output is correct |
39 |
Correct |
1 ms |
384 KB |
Output is correct |
40 |
Correct |
12 ms |
1536 KB |
Output is correct |
41 |
Correct |
269 ms |
26360 KB |
Output is correct |
42 |
Correct |
1 ms |
384 KB |
Output is correct |
43 |
Correct |
1 ms |
384 KB |
Output is correct |
44 |
Correct |
6 ms |
1024 KB |
Output is correct |
45 |
Correct |
131 ms |
14840 KB |
Output is correct |
46 |
Correct |
1 ms |
512 KB |
Output is correct |
47 |
Correct |
1 ms |
384 KB |
Output is correct |
48 |
Correct |
1 ms |
384 KB |
Output is correct |
49 |
Correct |
60 ms |
5880 KB |
Output is correct |
50 |
Correct |
249 ms |
22776 KB |
Output is correct |
51 |
Correct |
233 ms |
22264 KB |
Output is correct |
52 |
Correct |
275 ms |
25464 KB |
Output is correct |
53 |
Correct |
98 ms |
12312 KB |
Output is correct |
54 |
Correct |
104 ms |
12940 KB |
Output is correct |
55 |
Correct |
243 ms |
22264 KB |
Output is correct |
56 |
Correct |
260 ms |
24184 KB |
Output is correct |
57 |
Correct |
101 ms |
12408 KB |
Output is correct |
58 |
Correct |
1 ms |
384 KB |
Output is correct |
59 |
Correct |
1 ms |
384 KB |
Output is correct |
60 |
Correct |
1 ms |
384 KB |
Output is correct |
61 |
Correct |
62 ms |
5880 KB |
Output is correct |
62 |
Correct |
254 ms |
22904 KB |
Output is correct |
63 |
Correct |
233 ms |
22136 KB |
Output is correct |
64 |
Correct |
258 ms |
24184 KB |
Output is correct |
65 |
Correct |
1 ms |
384 KB |
Output is correct |
66 |
Correct |
65 ms |
6008 KB |
Output is correct |
67 |
Correct |
245 ms |
22648 KB |
Output is correct |
68 |
Correct |
237 ms |
22264 KB |
Output is correct |
69 |
Correct |
260 ms |
25208 KB |
Output is correct |
70 |
Correct |
1 ms |
384 KB |
Output is correct |
71 |
Correct |
1 ms |
384 KB |
Output is correct |
72 |
Correct |
1 ms |
384 KB |
Output is correct |
73 |
Correct |
60 ms |
5880 KB |
Output is correct |
74 |
Correct |
249 ms |
22776 KB |
Output is correct |
75 |
Correct |
240 ms |
22904 KB |
Output is correct |
76 |
Correct |
243 ms |
22392 KB |
Output is correct |
77 |
Correct |
243 ms |
22416 KB |
Output is correct |
78 |
Correct |
1 ms |
512 KB |
Output is correct |
79 |
Correct |
1 ms |
384 KB |
Output is correct |
80 |
Correct |
5 ms |
896 KB |
Output is correct |
81 |
Correct |
118 ms |
14328 KB |
Output is correct |
82 |
Correct |
1 ms |
384 KB |
Output is correct |
83 |
Correct |
1 ms |
384 KB |
Output is correct |
84 |
Correct |
1 ms |
384 KB |
Output is correct |
85 |
Correct |
60 ms |
5880 KB |
Output is correct |
86 |
Correct |
103 ms |
12792 KB |
Output is correct |
87 |
Correct |
99 ms |
12280 KB |
Output is correct |
88 |
Correct |
101 ms |
12536 KB |
Output is correct |
89 |
Correct |
98 ms |
12280 KB |
Output is correct |
90 |
Correct |
1 ms |
384 KB |
Output is correct |
91 |
Correct |
1 ms |
384 KB |
Output is correct |
92 |
Correct |
5 ms |
896 KB |
Output is correct |
93 |
Correct |
106 ms |
12152 KB |
Output is correct |
94 |
Correct |
1 ms |
384 KB |
Output is correct |
95 |
Correct |
1 ms |
384 KB |
Output is correct |
96 |
Correct |
1 ms |
512 KB |
Output is correct |
97 |
Correct |
26 ms |
3328 KB |
Output is correct |
98 |
Correct |
96 ms |
12152 KB |
Output is correct |
99 |
Correct |
95 ms |
12152 KB |
Output is correct |
100 |
Correct |
96 ms |
12296 KB |
Output is correct |
101 |
Correct |
98 ms |
12280 KB |
Output is correct |
102 |
Correct |
108 ms |
12280 KB |
Output is correct |
103 |
Correct |
113 ms |
12152 KB |
Output is correct |
104 |
Correct |
109 ms |
12152 KB |
Output is correct |
105 |
Correct |
110 ms |
12152 KB |
Output is correct |