#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
void build(vector<vector<int> > b) ;
void build(vector<vector<int> > b) ;
int Root(int x, vector<int> &root)
{
if (x == root[x]) return x;
return root[x] = Root(root[x], root);
}
void Merge(int v, int u, vector<int> &root, vector<int> &sz)
{
v = Root(v, root), u = Root(u, root);
if (v == u) return;
if (sz[v] > sz[u]) swap(v, u);
sz[u] += sz[v];
root[v] = u;
}
int construct(vector<vector<int> > p)
{
int n = p.size();
vector<int> root(n), sz(n);
for (int i = 0; i < n; i++) root[i] = i, sz[i] = 1;
int t = 0;
forn(i, n)
{
forn(j, n)
{
if (p[i][j])
{
Merge(i, j, root, sz);
}
}
}
forn(i, n)
{
forn(j, n)
{
if (Root(i, root) == Root(j, root) && p[i][j] == 0)
{
return 0;
}
}
}
vector<vector<int> > b(n, vector<int>(n));
forn(i, n)
{
vector<int> L;
forn(j, n)
{
if (Root(j, root) == i)
{
L.push_back(j);
}
}
vector<int> root2(L.size()), sz2(L.size());
iota(root2.begin(), root2.end(), 0);
fill(sz2.begin(), sz2.end(), 1);
for (int a = 0; a < L.size(); a++)
{
for (int b = 0; b < L.size(); b++)
{
if (p[L[a]][L[b]] == 1)
{
Merge(a, b, root2, sz2);
}
}
}
for (int a = 0; a < L.size(); a++)
{
for (int b = 0; b < L.size(); b++)
{
if (p[L[a]][L[b]] == 2 && Root(a, root2) == Root(b, root2))
return 0;
}
}
vector<vector<int> > z(L.size());
for (int a = 0; a < L.size(); a++)
{
z[Root(a, root2)].push_back(L[a]);
}
vector<int> q;
for (int j = 0; j < z.size(); j++)
{
if (z[j].size()) q.push_back(z[j][0]);
for (int e = 0; e + 1 < z[j].size(); e++)
{
b[z[j][e]][z[j][e + 1]] = 1;
b[z[j][e + 1]][z[j][e]] = 1;
}
}
if (q.size() == 2)
{
return 0;
}
if (q.size() > 2)
for (int i = 0; i < q.size(); i++)
{
b[q[i]][q[(i + 1) % q.size()]] = 1;
b[q[(i + 1) % q.size()]][q[i]] = 1;
}
}
build(b);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:32:5: note: in expansion of macro 'forn'
32 | forn(i, n)
| ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:34:9: note: in expansion of macro 'forn'
34 | forn(j, n)
| ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:42:5: note: in expansion of macro 'forn'
42 | forn(i, n)
| ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:44:9: note: in expansion of macro 'forn'
44 | forn(j, n)
| ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:53:5: note: in expansion of macro 'forn'
53 | forn(i, n)
| ^~~~
supertrees.cpp:5:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
5 | #define forn(i, n) for (int (i) = 0; (i) != (n); (i)++)
| ^
supertrees.cpp:56:9: note: in expansion of macro 'forn'
56 | forn(j, n)
| ^~~~
supertrees.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int a = 0; a < L.size(); a++)
| ~~^~~~~~~~~~
supertrees.cpp:68:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (int b = 0; b < L.size(); b++)
| ~~^~~~~~~~~~
supertrees.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for (int a = 0; a < L.size(); a++)
| ~~^~~~~~~~~~
supertrees.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int b = 0; b < L.size(); b++)
| ~~^~~~~~~~~~
supertrees.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int a = 0; a < L.size(); a++)
| ~~^~~~~~~~~~
supertrees.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int j = 0; j < z.size(); j++)
| ~~^~~~~~~~~~
supertrees.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int e = 0; e + 1 < z[j].size(); e++)
| ~~~~~~^~~~~~~~~~~~~
supertrees.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (int i = 0; i < q.size(); i++)
| ~~^~~~~~~~~~
supertrees.cpp:31:9: warning: unused variable 't' [-Wunused-variable]
31 | int t = 0;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
12 ms |
1152 KB |
Output is correct |
7 |
Correct |
306 ms |
22108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
12 ms |
1152 KB |
Output is correct |
7 |
Correct |
306 ms |
22108 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
280 ms |
22136 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
640 KB |
Output is correct |
17 |
Correct |
118 ms |
8184 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
65 ms |
5752 KB |
Output is correct |
21 |
Correct |
270 ms |
22136 KB |
Output is correct |
22 |
Correct |
266 ms |
22136 KB |
Output is correct |
23 |
Correct |
294 ms |
22136 KB |
Output is correct |
24 |
Correct |
247 ms |
22264 KB |
Output is correct |
25 |
Correct |
101 ms |
8184 KB |
Output is correct |
26 |
Correct |
95 ms |
8184 KB |
Output is correct |
27 |
Correct |
305 ms |
22232 KB |
Output is correct |
28 |
Correct |
252 ms |
22264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
10 ms |
1280 KB |
Output is correct |
9 |
Correct |
249 ms |
22136 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
13 ms |
1152 KB |
Output is correct |
13 |
Correct |
295 ms |
22136 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
640 KB |
Output is correct |
17 |
Correct |
123 ms |
8184 KB |
Output is correct |
18 |
Correct |
0 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
0 ms |
256 KB |
Output is correct |
21 |
Correct |
67 ms |
5752 KB |
Output is correct |
22 |
Correct |
274 ms |
22136 KB |
Output is correct |
23 |
Correct |
266 ms |
22104 KB |
Output is correct |
24 |
Correct |
292 ms |
22264 KB |
Output is correct |
25 |
Correct |
114 ms |
12244 KB |
Output is correct |
26 |
Correct |
105 ms |
8184 KB |
Output is correct |
27 |
Correct |
263 ms |
22136 KB |
Output is correct |
28 |
Correct |
300 ms |
22136 KB |
Output is correct |
29 |
Correct |
109 ms |
12152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
66 ms |
5752 KB |
Output is correct |
5 |
Correct |
263 ms |
22100 KB |
Output is correct |
6 |
Correct |
266 ms |
22136 KB |
Output is correct |
7 |
Correct |
298 ms |
22136 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
65 ms |
5752 KB |
Output is correct |
10 |
Correct |
268 ms |
22136 KB |
Output is correct |
11 |
Correct |
258 ms |
22136 KB |
Output is correct |
12 |
Correct |
292 ms |
22264 KB |
Output is correct |
13 |
Correct |
0 ms |
256 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
66 ms |
5752 KB |
Output is correct |
17 |
Correct |
265 ms |
22136 KB |
Output is correct |
18 |
Correct |
267 ms |
22136 KB |
Output is correct |
19 |
Correct |
269 ms |
22136 KB |
Output is correct |
20 |
Correct |
251 ms |
22136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
12 ms |
1152 KB |
Output is correct |
7 |
Correct |
306 ms |
22108 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
280 ms |
22136 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
640 KB |
Output is correct |
17 |
Correct |
118 ms |
8184 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
65 ms |
5752 KB |
Output is correct |
21 |
Correct |
270 ms |
22136 KB |
Output is correct |
22 |
Correct |
266 ms |
22136 KB |
Output is correct |
23 |
Correct |
294 ms |
22136 KB |
Output is correct |
24 |
Correct |
247 ms |
22264 KB |
Output is correct |
25 |
Correct |
101 ms |
8184 KB |
Output is correct |
26 |
Correct |
95 ms |
8184 KB |
Output is correct |
27 |
Correct |
305 ms |
22232 KB |
Output is correct |
28 |
Correct |
252 ms |
22264 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
0 ms |
256 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
256 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
249 ms |
22136 KB |
Output is correct |
38 |
Correct |
1 ms |
256 KB |
Output is correct |
39 |
Correct |
0 ms |
256 KB |
Output is correct |
40 |
Correct |
13 ms |
1152 KB |
Output is correct |
41 |
Correct |
295 ms |
22136 KB |
Output is correct |
42 |
Correct |
1 ms |
256 KB |
Output is correct |
43 |
Correct |
0 ms |
256 KB |
Output is correct |
44 |
Correct |
5 ms |
640 KB |
Output is correct |
45 |
Correct |
123 ms |
8184 KB |
Output is correct |
46 |
Correct |
0 ms |
256 KB |
Output is correct |
47 |
Correct |
0 ms |
256 KB |
Output is correct |
48 |
Correct |
0 ms |
256 KB |
Output is correct |
49 |
Correct |
67 ms |
5752 KB |
Output is correct |
50 |
Correct |
274 ms |
22136 KB |
Output is correct |
51 |
Correct |
266 ms |
22104 KB |
Output is correct |
52 |
Correct |
292 ms |
22264 KB |
Output is correct |
53 |
Correct |
114 ms |
12244 KB |
Output is correct |
54 |
Correct |
105 ms |
8184 KB |
Output is correct |
55 |
Correct |
263 ms |
22136 KB |
Output is correct |
56 |
Correct |
300 ms |
22136 KB |
Output is correct |
57 |
Correct |
109 ms |
12152 KB |
Output is correct |
58 |
Correct |
0 ms |
256 KB |
Output is correct |
59 |
Correct |
0 ms |
256 KB |
Output is correct |
60 |
Correct |
6 ms |
640 KB |
Output is correct |
61 |
Correct |
127 ms |
8188 KB |
Output is correct |
62 |
Correct |
0 ms |
256 KB |
Output is correct |
63 |
Correct |
0 ms |
256 KB |
Output is correct |
64 |
Correct |
0 ms |
256 KB |
Output is correct |
65 |
Correct |
65 ms |
5752 KB |
Output is correct |
66 |
Correct |
106 ms |
8184 KB |
Output is correct |
67 |
Correct |
100 ms |
8184 KB |
Output is correct |
68 |
Correct |
100 ms |
8184 KB |
Output is correct |
69 |
Correct |
111 ms |
12152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
0 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
12 ms |
1152 KB |
Output is correct |
7 |
Correct |
306 ms |
22108 KB |
Output is correct |
8 |
Correct |
0 ms |
256 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
0 ms |
256 KB |
Output is correct |
11 |
Correct |
0 ms |
256 KB |
Output is correct |
12 |
Correct |
10 ms |
1152 KB |
Output is correct |
13 |
Correct |
280 ms |
22136 KB |
Output is correct |
14 |
Correct |
0 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
640 KB |
Output is correct |
17 |
Correct |
118 ms |
8184 KB |
Output is correct |
18 |
Correct |
1 ms |
256 KB |
Output is correct |
19 |
Correct |
0 ms |
256 KB |
Output is correct |
20 |
Correct |
65 ms |
5752 KB |
Output is correct |
21 |
Correct |
270 ms |
22136 KB |
Output is correct |
22 |
Correct |
266 ms |
22136 KB |
Output is correct |
23 |
Correct |
294 ms |
22136 KB |
Output is correct |
24 |
Correct |
247 ms |
22264 KB |
Output is correct |
25 |
Correct |
101 ms |
8184 KB |
Output is correct |
26 |
Correct |
95 ms |
8184 KB |
Output is correct |
27 |
Correct |
305 ms |
22232 KB |
Output is correct |
28 |
Correct |
252 ms |
22264 KB |
Output is correct |
29 |
Correct |
1 ms |
256 KB |
Output is correct |
30 |
Correct |
1 ms |
256 KB |
Output is correct |
31 |
Correct |
1 ms |
384 KB |
Output is correct |
32 |
Correct |
0 ms |
256 KB |
Output is correct |
33 |
Correct |
0 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
256 KB |
Output is correct |
35 |
Correct |
1 ms |
256 KB |
Output is correct |
36 |
Correct |
10 ms |
1280 KB |
Output is correct |
37 |
Correct |
249 ms |
22136 KB |
Output is correct |
38 |
Correct |
1 ms |
256 KB |
Output is correct |
39 |
Correct |
0 ms |
256 KB |
Output is correct |
40 |
Correct |
13 ms |
1152 KB |
Output is correct |
41 |
Correct |
295 ms |
22136 KB |
Output is correct |
42 |
Correct |
1 ms |
256 KB |
Output is correct |
43 |
Correct |
0 ms |
256 KB |
Output is correct |
44 |
Correct |
5 ms |
640 KB |
Output is correct |
45 |
Correct |
123 ms |
8184 KB |
Output is correct |
46 |
Correct |
0 ms |
256 KB |
Output is correct |
47 |
Correct |
0 ms |
256 KB |
Output is correct |
48 |
Correct |
0 ms |
256 KB |
Output is correct |
49 |
Correct |
67 ms |
5752 KB |
Output is correct |
50 |
Correct |
274 ms |
22136 KB |
Output is correct |
51 |
Correct |
266 ms |
22104 KB |
Output is correct |
52 |
Correct |
292 ms |
22264 KB |
Output is correct |
53 |
Correct |
114 ms |
12244 KB |
Output is correct |
54 |
Correct |
105 ms |
8184 KB |
Output is correct |
55 |
Correct |
263 ms |
22136 KB |
Output is correct |
56 |
Correct |
300 ms |
22136 KB |
Output is correct |
57 |
Correct |
109 ms |
12152 KB |
Output is correct |
58 |
Correct |
0 ms |
256 KB |
Output is correct |
59 |
Correct |
0 ms |
256 KB |
Output is correct |
60 |
Correct |
1 ms |
256 KB |
Output is correct |
61 |
Correct |
66 ms |
5752 KB |
Output is correct |
62 |
Correct |
263 ms |
22100 KB |
Output is correct |
63 |
Correct |
266 ms |
22136 KB |
Output is correct |
64 |
Correct |
298 ms |
22136 KB |
Output is correct |
65 |
Correct |
0 ms |
256 KB |
Output is correct |
66 |
Correct |
65 ms |
5752 KB |
Output is correct |
67 |
Correct |
268 ms |
22136 KB |
Output is correct |
68 |
Correct |
258 ms |
22136 KB |
Output is correct |
69 |
Correct |
292 ms |
22264 KB |
Output is correct |
70 |
Correct |
0 ms |
256 KB |
Output is correct |
71 |
Correct |
0 ms |
256 KB |
Output is correct |
72 |
Correct |
0 ms |
384 KB |
Output is correct |
73 |
Correct |
66 ms |
5752 KB |
Output is correct |
74 |
Correct |
265 ms |
22136 KB |
Output is correct |
75 |
Correct |
267 ms |
22136 KB |
Output is correct |
76 |
Correct |
269 ms |
22136 KB |
Output is correct |
77 |
Correct |
251 ms |
22136 KB |
Output is correct |
78 |
Correct |
0 ms |
256 KB |
Output is correct |
79 |
Correct |
0 ms |
256 KB |
Output is correct |
80 |
Correct |
6 ms |
640 KB |
Output is correct |
81 |
Correct |
127 ms |
8188 KB |
Output is correct |
82 |
Correct |
0 ms |
256 KB |
Output is correct |
83 |
Correct |
0 ms |
256 KB |
Output is correct |
84 |
Correct |
0 ms |
256 KB |
Output is correct |
85 |
Correct |
65 ms |
5752 KB |
Output is correct |
86 |
Correct |
106 ms |
8184 KB |
Output is correct |
87 |
Correct |
100 ms |
8184 KB |
Output is correct |
88 |
Correct |
100 ms |
8184 KB |
Output is correct |
89 |
Correct |
111 ms |
12152 KB |
Output is correct |
90 |
Correct |
1 ms |
256 KB |
Output is correct |
91 |
Correct |
0 ms |
256 KB |
Output is correct |
92 |
Correct |
6 ms |
640 KB |
Output is correct |
93 |
Correct |
120 ms |
8188 KB |
Output is correct |
94 |
Incorrect |
0 ms |
256 KB |
Answer gives possible 1 while actual possible 0 |
95 |
Halted |
0 ms |
0 KB |
- |