#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, x, y, i, j, first, last, sef1, sef2;
dsu forest1, forest2;
vector <int> f1[MAX_N], f2[MAX_N];
n = p.size();
vector <vector <int>> b( n );
forest1.init( n );
forest2.init( n );
for ( x = 0; x < n; x++ ) {
for ( y = 0; y < n; y++ ) {
if ( p[x][y] >= 1 )
forest1.unionn( x, y );
if ( p[x][y] == 1 )
forest2.unionn( x, y );
}
}
for ( x = 0; x < n; x++ ) {
f1[forest1.find( x )].push_back( x );
f2[forest2.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 ( f1[x].size() > 1 ) {
int e2;
e2 = 0;
for ( i = 0; i < f1[x].size(); i++ ) {
for ( j = i + 1; j < f1[x].size(); j++ ) {
if ( p[f1[x][i]][f1[x][j]] == 0 )
return 0;
if ( p[f1[x][i]][f1[x][j]] == 2 )
e2 = 1;
}
}
if ( e2 ) {
sef1 = sef2 = -1;
for ( i = 0; i < f1[x].size(); i++ ) {
if ( forest2.find( f1[x][i] ) != f1[x][i] && forest2.find( f1[x][i] ) != sef1 && forest2.find( f1[x][i] ) != sef2 ) {
if ( sef1 == -1 )
sef1 = forest2.find( f1[x][i] );
else if ( sef2 == -1 )
sef2 = forest2.find( f1[x][i] );
else
return 0;
}
}
first = -1;
last = -1;
for ( i = 0; i < f1[x].size(); i++ ) {
if ( forest2.find( f1[x][i] ) != f1[x][i] ) {
b[f1[x][i]][forest2.find( f1[x][i] )] = 1;
b[forest2.find( f1[x][i] )][f1[x][i]] = 1;
} else {
if ( last != -1 ) {
b[last][f1[x][i]] = 1;
b[f1[x][i]][last] = 1;
}
if ( first == -1 )
first = f1[x][i];
last = f1[x][i];
}
}
if ( first != last ) {
b[first][last] = 1;
b[last][first] = 1;
} else
return 0;
for ( i = 0; i < f1[x].size(); i++ ) {
for ( j = i + 1; j < f1[x].size(); j++ ) {
if ( forest2.find( f1[x][i] ) == forest2.find( f1[x][j] ) ) {
if ( p[f1[x][i]][f1[x][j]] != 1 )
return 0;
} else {
if ( p[f1[x][i]][f1[x][j]] != 2 )
return 0;
}
}
}
} else {
for ( i = 0; i < f1[x].size() - 1; i++ ) {
b[f1[x][i]][f1[x][i + 1]] = 1;
b[f1[x][i + 1]][f1[x][i]] = 1;
}
}
}
}
build( b );
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:69:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for ( i = 0; i < f1[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:70:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for ( j = i + 1; j < f1[x].size(); j++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:79:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for ( i = 0; i < f1[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:91:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for ( i = 0; i < f1[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for ( i = 0; i < f1[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:111:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for ( j = i + 1; j < f1[x].size(); j++ ) {
| ~~^~~~~~~~~~~~~~
supertrees.cpp:122:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for ( i = 0; i < f1[x].size() - 1; i++ ) {
| ~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1184 KB |
Output is correct |
7 |
Correct |
194 ms |
22144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1184 KB |
Output is correct |
7 |
Correct |
194 ms |
22144 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
1244 KB |
Output is correct |
13 |
Correct |
190 ms |
22140 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
106 ms |
12168 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
47 ms |
5828 KB |
Output is correct |
21 |
Correct |
187 ms |
22148 KB |
Output is correct |
22 |
Correct |
185 ms |
22140 KB |
Output is correct |
23 |
Correct |
202 ms |
22136 KB |
Output is correct |
24 |
Correct |
186 ms |
22152 KB |
Output is correct |
25 |
Correct |
88 ms |
12168 KB |
Output is correct |
26 |
Correct |
84 ms |
12284 KB |
Output is correct |
27 |
Correct |
202 ms |
22140 KB |
Output is correct |
28 |
Correct |
183 ms |
22136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Incorrect |
0 ms |
332 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
49 ms |
5760 KB |
Output is correct |
5 |
Correct |
193 ms |
22204 KB |
Output is correct |
6 |
Correct |
184 ms |
22212 KB |
Output is correct |
7 |
Correct |
197 ms |
22240 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
48 ms |
5736 KB |
Output is correct |
10 |
Correct |
185 ms |
22148 KB |
Output is correct |
11 |
Correct |
182 ms |
22140 KB |
Output is correct |
12 |
Correct |
193 ms |
22212 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Incorrect |
22 ms |
3276 KB |
Answer gives possible 0 while actual possible 1 |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1184 KB |
Output is correct |
7 |
Correct |
194 ms |
22144 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
1244 KB |
Output is correct |
13 |
Correct |
190 ms |
22140 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
106 ms |
12168 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
47 ms |
5828 KB |
Output is correct |
21 |
Correct |
187 ms |
22148 KB |
Output is correct |
22 |
Correct |
185 ms |
22140 KB |
Output is correct |
23 |
Correct |
202 ms |
22136 KB |
Output is correct |
24 |
Correct |
186 ms |
22152 KB |
Output is correct |
25 |
Correct |
88 ms |
12168 KB |
Output is correct |
26 |
Correct |
84 ms |
12284 KB |
Output is correct |
27 |
Correct |
202 ms |
22140 KB |
Output is correct |
28 |
Correct |
183 ms |
22136 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
0 ms |
332 KB |
Output is correct |
32 |
Incorrect |
0 ms |
332 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
8 ms |
1184 KB |
Output is correct |
7 |
Correct |
194 ms |
22144 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
1244 KB |
Output is correct |
13 |
Correct |
190 ms |
22140 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
4 ms |
844 KB |
Output is correct |
17 |
Correct |
106 ms |
12168 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
47 ms |
5828 KB |
Output is correct |
21 |
Correct |
187 ms |
22148 KB |
Output is correct |
22 |
Correct |
185 ms |
22140 KB |
Output is correct |
23 |
Correct |
202 ms |
22136 KB |
Output is correct |
24 |
Correct |
186 ms |
22152 KB |
Output is correct |
25 |
Correct |
88 ms |
12168 KB |
Output is correct |
26 |
Correct |
84 ms |
12284 KB |
Output is correct |
27 |
Correct |
202 ms |
22140 KB |
Output is correct |
28 |
Correct |
183 ms |
22136 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
0 ms |
332 KB |
Output is correct |
32 |
Incorrect |
0 ms |
332 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |