#include "supertrees.h"
#ifdef ngu
#include "grader.cpp"
#endif // ngu
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
auto valid = [&] (vector<int> a, vector<int> b, int c) {
for(int &j : a) for(int &k : b) if (p[j][k] != c) return false;
return true;
};
vector<int> vis(n), arr;
auto dfs = [&] (auto self, int u) -> void {
vis[u] = 1;
arr.push_back(u);
for(int v = 0; v < n; v++) if (!vis[v] && p[u][v] == 1) self(self, v);
};
std::vector<std::vector<int>> answer(n, vector<int> (n));
auto add = [&] (int u, int v) {
answer[u][v] = answer[v][u] = 1;
};
vector<vector<int> > connected;
for(int i = 0; i < n; i++) if (!vis[i]) {
arr.clear();
dfs(dfs, i);
if (!valid(arr, arr, 1)) return 0;
connected.push_back(arr);
for(int j = 1; j < arr.size(); j++) {
answer[arr[j]][arr[j - 1]] = answer[arr[j - 1]][arr[j]] = 1;
}
}
for(int i = 0; i < n; i++) vis[i] = 0;
for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
vector<int> zip, g;
g.push_back(i);
for(auto &k : connected[i]) zip.push_back(k);
for(int j = 0; j < connected.size(); j++) if (j != i && p[connected[i][0]][connected[j][0]] == 2) {
if (vis[j]) return 0;
if (!valid(zip, connected[j], 2)) return 0;
for(auto &k : connected[j]) zip.push_back(k);
g.push_back(j);
}
if (g.size() == 1) continue;
if (g.size() < 3) return 0;
for(int i = 1; i < g.size(); i++) {
add(connected[g[i]][0], connected[g[i - 1]][0]);
}
add(connected[g[0]][0], connected[g.back()][0]);
}
build(answer);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int j = 1; j < arr.size(); j++) {
| ~~^~~~~~~~~~~~
supertrees.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0; i < connected.size(); i++) if (!vis[i]) {
| ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int j = 0; j < connected.size(); j++) if (j != i && p[connected[i][0]][connected[j][0]] == 2) {
| ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 1; i < g.size(); i++) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
1116 KB |
Output is correct |
7 |
Correct |
148 ms |
22036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
1116 KB |
Output is correct |
7 |
Correct |
148 ms |
22036 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
9 ms |
1372 KB |
Output is correct |
13 |
Correct |
156 ms |
22024 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
69 ms |
12312 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
47 ms |
5836 KB |
Output is correct |
21 |
Correct |
153 ms |
22176 KB |
Output is correct |
22 |
Correct |
154 ms |
21996 KB |
Output is correct |
23 |
Correct |
152 ms |
22036 KB |
Output is correct |
24 |
Correct |
154 ms |
22096 KB |
Output is correct |
25 |
Correct |
68 ms |
12036 KB |
Output is correct |
26 |
Correct |
63 ms |
12040 KB |
Output is correct |
27 |
Correct |
158 ms |
21980 KB |
Output is correct |
28 |
Correct |
161 ms |
22192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
7 ms |
1108 KB |
Output is correct |
9 |
Correct |
154 ms |
22080 KB |
Output is correct |
10 |
Incorrect |
0 ms |
344 KB |
Too many ways to get from 0 to 3, should be 2 found no less than 3 |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
40 ms |
5868 KB |
Output is correct |
5 |
Correct |
153 ms |
22100 KB |
Output is correct |
6 |
Correct |
153 ms |
22044 KB |
Output is correct |
7 |
Correct |
162 ms |
22100 KB |
Output is correct |
8 |
Incorrect |
0 ms |
344 KB |
Too many ways to get from 0 to 2, should be 2 found no less than 3 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
1116 KB |
Output is correct |
7 |
Correct |
148 ms |
22036 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
9 ms |
1372 KB |
Output is correct |
13 |
Correct |
156 ms |
22024 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
69 ms |
12312 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
47 ms |
5836 KB |
Output is correct |
21 |
Correct |
153 ms |
22176 KB |
Output is correct |
22 |
Correct |
154 ms |
21996 KB |
Output is correct |
23 |
Correct |
152 ms |
22036 KB |
Output is correct |
24 |
Correct |
154 ms |
22096 KB |
Output is correct |
25 |
Correct |
68 ms |
12036 KB |
Output is correct |
26 |
Correct |
63 ms |
12040 KB |
Output is correct |
27 |
Correct |
158 ms |
21980 KB |
Output is correct |
28 |
Correct |
161 ms |
22192 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
7 ms |
1108 KB |
Output is correct |
37 |
Correct |
154 ms |
22080 KB |
Output is correct |
38 |
Incorrect |
0 ms |
344 KB |
Too many ways to get from 0 to 3, should be 2 found no less than 3 |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
1116 KB |
Output is correct |
7 |
Correct |
148 ms |
22036 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
9 ms |
1372 KB |
Output is correct |
13 |
Correct |
156 ms |
22024 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
3 ms |
856 KB |
Output is correct |
17 |
Correct |
69 ms |
12312 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
47 ms |
5836 KB |
Output is correct |
21 |
Correct |
153 ms |
22176 KB |
Output is correct |
22 |
Correct |
154 ms |
21996 KB |
Output is correct |
23 |
Correct |
152 ms |
22036 KB |
Output is correct |
24 |
Correct |
154 ms |
22096 KB |
Output is correct |
25 |
Correct |
68 ms |
12036 KB |
Output is correct |
26 |
Correct |
63 ms |
12040 KB |
Output is correct |
27 |
Correct |
158 ms |
21980 KB |
Output is correct |
28 |
Correct |
161 ms |
22192 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
348 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
344 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
7 ms |
1108 KB |
Output is correct |
37 |
Correct |
154 ms |
22080 KB |
Output is correct |
38 |
Incorrect |
0 ms |
344 KB |
Too many ways to get from 0 to 3, should be 2 found no less than 3 |
39 |
Halted |
0 ms |
0 KB |
- |