#include "supertrees.h"
#include <vector>
#include <set>
#include <iostream>
using namespace std;
vector<int> parent(1003);
int find_head(int n){
if(parent[n] == n){
return n;
}return find_head(parent[n]);
}
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
set<int> heads;
vector<vector<int>>ans(n,vector<int>(n,0));
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)
continue;
if(p[i][j] == 3){
return 0;
}else if(p[i][j] == 1){
int lower = min(i,j);
int higher = max(i,j);
if(find_head(lower) != find_head(higher)){
ans[i][j] = 1;
ans[j][i] = 1;
parent[higher] = find_head(lower);
}
}else if(p[i][j] == 2){
heads.insert(find_head(i));
heads.insert(find_head(j));
}
}
}
// cout << "table travers" << endl;
vector<int> header;
for (int i : heads) {
header.push_back(i);
}
int t = header.size();
// cout << t << " " << (0<(t-1)) << endl;
for (int i = 0; i < (t-1); i++) {
// cout << "for" << endl;
ans[header[i]][header[i+1]] = 1;
ans[header[i+1]][header[i]] = 1;
}
if(t > 2){
// cout << "comare" << endl;
ans[header[0]][header[t-1]] = 1;
ans[header[t-1]][header[0]] = 1;
}
// cout << "headers connected" << endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int i_head = find_head(i);
int j_head = find_head(j);
if(i==j)
continue;
if(p[i][j] == 0){
if(i_head == j_head){
return 0;
}
if(heads.count(i_head) == 1 and heads.count(j_head) == 1){
return 0;
}
}else if(p[i][j] == 1){
if(i_head != j_head){
return 0;
}
}else if(p[i][j] == 2){
if(t < 3){
return 0;
}
if(i_head == j_head){
return 0;
}
if(heads.count(i_head) == 0 or heads.count(j_head) == 0){
return 0;
}
}
}
}
build(ans);
return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
7 ms |
1212 KB |
Output is correct |
7 |
Correct |
184 ms |
22372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
7 ms |
1212 KB |
Output is correct |
7 |
Correct |
184 ms |
22372 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
151 ms |
22332 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
76 ms |
12304 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
39 ms |
5936 KB |
Output is correct |
21 |
Correct |
154 ms |
22196 KB |
Output is correct |
22 |
Correct |
189 ms |
22232 KB |
Output is correct |
23 |
Correct |
159 ms |
22188 KB |
Output is correct |
24 |
Correct |
186 ms |
22280 KB |
Output is correct |
25 |
Correct |
68 ms |
12332 KB |
Output is correct |
26 |
Correct |
59 ms |
12336 KB |
Output is correct |
27 |
Correct |
157 ms |
22304 KB |
Output is correct |
28 |
Correct |
160 ms |
22212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
7 ms |
1240 KB |
Output is correct |
9 |
Correct |
151 ms |
22160 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
10 ms |
1236 KB |
Output is correct |
13 |
Correct |
247 ms |
22116 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
5 ms |
800 KB |
Output is correct |
17 |
Correct |
103 ms |
12440 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
300 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Incorrect |
16 ms |
3360 KB |
Answer gives possible 0 while actual possible 1 |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
40 ms |
5908 KB |
Output is correct |
5 |
Correct |
158 ms |
22412 KB |
Output is correct |
6 |
Correct |
154 ms |
22292 KB |
Output is correct |
7 |
Correct |
159 ms |
22276 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Incorrect |
17 ms |
3428 KB |
Answer gives possible 0 while actual possible 1 |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
7 ms |
1212 KB |
Output is correct |
7 |
Correct |
184 ms |
22372 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
151 ms |
22332 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
76 ms |
12304 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
39 ms |
5936 KB |
Output is correct |
21 |
Correct |
154 ms |
22196 KB |
Output is correct |
22 |
Correct |
189 ms |
22232 KB |
Output is correct |
23 |
Correct |
159 ms |
22188 KB |
Output is correct |
24 |
Correct |
186 ms |
22280 KB |
Output is correct |
25 |
Correct |
68 ms |
12332 KB |
Output is correct |
26 |
Correct |
59 ms |
12336 KB |
Output is correct |
27 |
Correct |
157 ms |
22304 KB |
Output is correct |
28 |
Correct |
160 ms |
22212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
304 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
7 ms |
1240 KB |
Output is correct |
37 |
Correct |
151 ms |
22160 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
10 ms |
1236 KB |
Output is correct |
41 |
Correct |
247 ms |
22116 KB |
Output is correct |
42 |
Correct |
1 ms |
304 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
5 ms |
800 KB |
Output is correct |
45 |
Correct |
103 ms |
12440 KB |
Output is correct |
46 |
Correct |
0 ms |
212 KB |
Output is correct |
47 |
Correct |
1 ms |
300 KB |
Output is correct |
48 |
Correct |
1 ms |
212 KB |
Output is correct |
49 |
Incorrect |
16 ms |
3360 KB |
Answer gives possible 0 while actual possible 1 |
50 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
7 ms |
1212 KB |
Output is correct |
7 |
Correct |
184 ms |
22372 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
7 ms |
1236 KB |
Output is correct |
13 |
Correct |
151 ms |
22332 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
304 KB |
Output is correct |
16 |
Correct |
3 ms |
852 KB |
Output is correct |
17 |
Correct |
76 ms |
12304 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
39 ms |
5936 KB |
Output is correct |
21 |
Correct |
154 ms |
22196 KB |
Output is correct |
22 |
Correct |
189 ms |
22232 KB |
Output is correct |
23 |
Correct |
159 ms |
22188 KB |
Output is correct |
24 |
Correct |
186 ms |
22280 KB |
Output is correct |
25 |
Correct |
68 ms |
12332 KB |
Output is correct |
26 |
Correct |
59 ms |
12336 KB |
Output is correct |
27 |
Correct |
157 ms |
22304 KB |
Output is correct |
28 |
Correct |
160 ms |
22212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
304 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
1 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
7 ms |
1240 KB |
Output is correct |
37 |
Correct |
151 ms |
22160 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
10 ms |
1236 KB |
Output is correct |
41 |
Correct |
247 ms |
22116 KB |
Output is correct |
42 |
Correct |
1 ms |
304 KB |
Output is correct |
43 |
Correct |
1 ms |
212 KB |
Output is correct |
44 |
Correct |
5 ms |
800 KB |
Output is correct |
45 |
Correct |
103 ms |
12440 KB |
Output is correct |
46 |
Correct |
0 ms |
212 KB |
Output is correct |
47 |
Correct |
1 ms |
300 KB |
Output is correct |
48 |
Correct |
1 ms |
212 KB |
Output is correct |
49 |
Incorrect |
16 ms |
3360 KB |
Answer gives possible 0 while actual possible 1 |
50 |
Halted |
0 ms |
0 KB |
- |