#include <iostream>
#include <vector>
#include "supertrees.h"
#define MAX_N 1000
using namespace std;
struct dsu {
int n;
int sef[MAX_N];
void init( int x ) {
int i;
n = x;
for ( i = 0; i < n; i++ )
sef[i] = i;
}
int find( int x ) {
if ( sef[x] != x )
sef[x] = find( sef[x] );
return sef[x];
}
void unionn( int x, int y ) {
x = find( x );
y = find( y );
sef[y] = x;
}
};
int construct( vector <vector <int>> p ) {
int n, a, x, y, i, j;
dsu forest;
vector <int> f[MAX_N];
n = p.size();
vector <vector <int>> b( n );
forest.init( n );
for ( x = 0; x < n; x++ ) {
for ( y = 0; y < n; y++ ) {
if ( p[x][y] > 0 )
forest.unionn( x, y );
}
}
for ( x = 0; x < n; x++ )
f[forest.find( x )].push_back( x );
for ( i = 0; i < n; i++ ) {
for ( j = 0; j < n; j++ )
b[i].push_back( 0 );
}
for ( x = 0; x < n; x++ ) {
if ( f[x].size() ) {
a = p[f[x][0]][f[x][f[x].size() - 1]];
for ( i = 0; i < f[x].size(); i++ ) {
for ( j = i + 1; j < f[x].size(); j++ ) {
if ( a != p[f[x][i]][f[x][j]] )
return 0;
}
}
for ( i = 0; i < f[x].size() - 1; i++ ) {
b[f[x][i]][f[x][i + 1]] = 1;
b[f[x][i + 1]][f[x][i]] = 1;
}
if ( a == 2 && f[x].size() <= 2 )
return 0;
if ( a == 2 ) {
b[f[x][0]][f[x][f[x].size() - 1]] = 1;
b[f[x][f[x].size() - 1]][f[x][0]] = 1;
}
}
}
build( b );
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for ( i = 0; i < f[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~
supertrees.cpp:62:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for ( j = i + 1; j < f[x].size(); j++ ) {
| ~~^~~~~~~~~~~~~
supertrees.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for ( i = 0; i < f[x].size() - 1; i++ ) {
| ~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1328 KB |
Output is correct |
7 |
Correct |
171 ms |
23860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1328 KB |
Output is correct |
7 |
Correct |
171 ms |
23860 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
9 ms |
1232 KB |
Output is correct |
13 |
Correct |
177 ms |
23776 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
87 ms |
14188 KB |
Output is correct |
18 |
Correct |
1 ms |
272 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
50 ms |
6212 KB |
Output is correct |
21 |
Correct |
185 ms |
23812 KB |
Output is correct |
22 |
Correct |
184 ms |
23864 KB |
Output is correct |
23 |
Correct |
186 ms |
23844 KB |
Output is correct |
24 |
Correct |
175 ms |
23840 KB |
Output is correct |
25 |
Correct |
105 ms |
14148 KB |
Output is correct |
26 |
Correct |
70 ms |
14184 KB |
Output is correct |
27 |
Correct |
187 ms |
23864 KB |
Output is correct |
28 |
Correct |
173 ms |
23804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
288 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
8 ms |
1292 KB |
Output is correct |
9 |
Correct |
171 ms |
24228 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
292 KB |
Output is correct |
12 |
Correct |
8 ms |
1228 KB |
Output is correct |
13 |
Correct |
189 ms |
24128 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
808 KB |
Output is correct |
17 |
Correct |
87 ms |
14156 KB |
Output is correct |
18 |
Correct |
1 ms |
292 KB |
Output is correct |
19 |
Correct |
0 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
41 ms |
6212 KB |
Output is correct |
22 |
Correct |
190 ms |
24056 KB |
Output is correct |
23 |
Correct |
178 ms |
24048 KB |
Output is correct |
24 |
Correct |
186 ms |
24040 KB |
Output is correct |
25 |
Correct |
69 ms |
14188 KB |
Output is correct |
26 |
Correct |
87 ms |
14196 KB |
Output is correct |
27 |
Correct |
165 ms |
24100 KB |
Output is correct |
28 |
Correct |
183 ms |
24104 KB |
Output is correct |
29 |
Correct |
66 ms |
14148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
272 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
272 KB |
Output is correct |
4 |
Correct |
51 ms |
6236 KB |
Output is correct |
5 |
Correct |
207 ms |
23844 KB |
Output is correct |
6 |
Correct |
175 ms |
23876 KB |
Output is correct |
7 |
Correct |
187 ms |
23820 KB |
Output is correct |
8 |
Correct |
1 ms |
288 KB |
Output is correct |
9 |
Correct |
44 ms |
6260 KB |
Output is correct |
10 |
Correct |
174 ms |
23808 KB |
Output is correct |
11 |
Correct |
170 ms |
23748 KB |
Output is correct |
12 |
Correct |
199 ms |
23928 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
288 KB |
Output is correct |
15 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1328 KB |
Output is correct |
7 |
Correct |
171 ms |
23860 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
9 ms |
1232 KB |
Output is correct |
13 |
Correct |
177 ms |
23776 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
87 ms |
14188 KB |
Output is correct |
18 |
Correct |
1 ms |
272 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
50 ms |
6212 KB |
Output is correct |
21 |
Correct |
185 ms |
23812 KB |
Output is correct |
22 |
Correct |
184 ms |
23864 KB |
Output is correct |
23 |
Correct |
186 ms |
23844 KB |
Output is correct |
24 |
Correct |
175 ms |
23840 KB |
Output is correct |
25 |
Correct |
105 ms |
14148 KB |
Output is correct |
26 |
Correct |
70 ms |
14184 KB |
Output is correct |
27 |
Correct |
187 ms |
23864 KB |
Output is correct |
28 |
Correct |
173 ms |
23804 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
288 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
8 ms |
1292 KB |
Output is correct |
37 |
Correct |
171 ms |
24228 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
292 KB |
Output is correct |
40 |
Correct |
8 ms |
1228 KB |
Output is correct |
41 |
Correct |
189 ms |
24128 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
4 ms |
808 KB |
Output is correct |
45 |
Correct |
87 ms |
14156 KB |
Output is correct |
46 |
Correct |
1 ms |
292 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
41 ms |
6212 KB |
Output is correct |
50 |
Correct |
190 ms |
24056 KB |
Output is correct |
51 |
Correct |
178 ms |
24048 KB |
Output is correct |
52 |
Correct |
186 ms |
24040 KB |
Output is correct |
53 |
Correct |
69 ms |
14188 KB |
Output is correct |
54 |
Correct |
87 ms |
14196 KB |
Output is correct |
55 |
Correct |
165 ms |
24100 KB |
Output is correct |
56 |
Correct |
183 ms |
24104 KB |
Output is correct |
57 |
Correct |
66 ms |
14148 KB |
Output is correct |
58 |
Correct |
1 ms |
292 KB |
Output is correct |
59 |
Correct |
1 ms |
204 KB |
Output is correct |
60 |
Correct |
4 ms |
920 KB |
Output is correct |
61 |
Correct |
101 ms |
14148 KB |
Output is correct |
62 |
Correct |
1 ms |
288 KB |
Output is correct |
63 |
Correct |
0 ms |
204 KB |
Output is correct |
64 |
Correct |
1 ms |
280 KB |
Output is correct |
65 |
Incorrect |
23 ms |
3788 KB |
Answer gives possible 0 while actual possible 1 |
66 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
8 ms |
1328 KB |
Output is correct |
7 |
Correct |
171 ms |
23860 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
9 ms |
1232 KB |
Output is correct |
13 |
Correct |
177 ms |
23776 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
87 ms |
14188 KB |
Output is correct |
18 |
Correct |
1 ms |
272 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
50 ms |
6212 KB |
Output is correct |
21 |
Correct |
185 ms |
23812 KB |
Output is correct |
22 |
Correct |
184 ms |
23864 KB |
Output is correct |
23 |
Correct |
186 ms |
23844 KB |
Output is correct |
24 |
Correct |
175 ms |
23840 KB |
Output is correct |
25 |
Correct |
105 ms |
14148 KB |
Output is correct |
26 |
Correct |
70 ms |
14184 KB |
Output is correct |
27 |
Correct |
187 ms |
23864 KB |
Output is correct |
28 |
Correct |
173 ms |
23804 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
1 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
288 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
8 ms |
1292 KB |
Output is correct |
37 |
Correct |
171 ms |
24228 KB |
Output is correct |
38 |
Correct |
1 ms |
204 KB |
Output is correct |
39 |
Correct |
1 ms |
292 KB |
Output is correct |
40 |
Correct |
8 ms |
1228 KB |
Output is correct |
41 |
Correct |
189 ms |
24128 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
4 ms |
808 KB |
Output is correct |
45 |
Correct |
87 ms |
14156 KB |
Output is correct |
46 |
Correct |
1 ms |
292 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
1 ms |
204 KB |
Output is correct |
49 |
Correct |
41 ms |
6212 KB |
Output is correct |
50 |
Correct |
190 ms |
24056 KB |
Output is correct |
51 |
Correct |
178 ms |
24048 KB |
Output is correct |
52 |
Correct |
186 ms |
24040 KB |
Output is correct |
53 |
Correct |
69 ms |
14188 KB |
Output is correct |
54 |
Correct |
87 ms |
14196 KB |
Output is correct |
55 |
Correct |
165 ms |
24100 KB |
Output is correct |
56 |
Correct |
183 ms |
24104 KB |
Output is correct |
57 |
Correct |
66 ms |
14148 KB |
Output is correct |
58 |
Correct |
1 ms |
272 KB |
Output is correct |
59 |
Correct |
0 ms |
204 KB |
Output is correct |
60 |
Correct |
1 ms |
272 KB |
Output is correct |
61 |
Correct |
51 ms |
6236 KB |
Output is correct |
62 |
Correct |
207 ms |
23844 KB |
Output is correct |
63 |
Correct |
175 ms |
23876 KB |
Output is correct |
64 |
Correct |
187 ms |
23820 KB |
Output is correct |
65 |
Correct |
1 ms |
288 KB |
Output is correct |
66 |
Correct |
44 ms |
6260 KB |
Output is correct |
67 |
Correct |
174 ms |
23808 KB |
Output is correct |
68 |
Correct |
170 ms |
23748 KB |
Output is correct |
69 |
Correct |
199 ms |
23928 KB |
Output is correct |
70 |
Correct |
1 ms |
204 KB |
Output is correct |
71 |
Correct |
1 ms |
288 KB |
Output is correct |
72 |
Incorrect |
0 ms |
204 KB |
Answer gives possible 0 while actual possible 1 |
73 |
Halted |
0 ms |
0 KB |
- |