#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define s second
int visited[2000];
vector<vector<int> > adjlist;
int coun=1;
void dfs(int s){
visited[s]=coun;
for(int i=0; i<adjlist[s].size(); i++){
int v=adjlist[s][i];
if(visited[v]==0)
dfs(v);
}
}
int construct(vector<vector<int> > p) {
int n = p.size();
bool check = true;
for(int i = 0;i<n;i++) {
for(int j = 0;j<n;j++) {
if(i == j)continue;
if(p[i][j] == 1)check = false;
}
}
if(!check) {
vector< vector< int > > ans(n, vector< int >(n));
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (p[i][j] == 3)
return 0;
vector< int > siv(n, false);
vector< int > vis(n, false);
for (int i = 0; i < n; ++i)
if (not vis[i])
{
vector< int > sub;
for (int j = 0; j < n; ++j)
if (p[i][j] and not vis[j])
sub.push_back(j);
else if (p[i][j] and vis[j]) return 0;
for (int a : sub)
vis[a] = true;
for (int a : sub)
for (int j = 0; j < n; ++j)
if (not vis[j] and p[a][j])
return 0;
for (int a : sub)
for (int b : sub)
if (not p[a][b])
return 0;
vector< vector< int > > div;
for (int a : sub)
if (not siv[a])
{
div.push_back(vector< int >());
for (int b : sub)
if (p[a][b] == 1 and not siv[b])
div.back().push_back(b);
else if (p[a][b] == 1 and siv[b]) return 0;
for (int a : div.back())
siv[a] = true;
for (int a : div.back())
for (int b : sub)
if (not siv[b] and p[a][b] == 1)
return 0;
for (int a : div.back())
for (int b : div.back())
if (p[a][b] != 1)
return 0;
}
for (int i = 1; i < div.size(); ++i)
ans[div[i - 1][0]][div[i][0]] = ans[div[i][0]][div[i - 1][0]] = 1;
if (div.size() > 1)
ans[div.back()[0]][div.front()[0]] = ans[div.front()[0]][div.back()[0]] = 1;
for (const auto& vv : div)
for (int i = 1; i < vv.size(); ++i)
ans[vv[i]][vv[i - 1]] = ans[vv[i - 1]][vv[i]] = 1;
}
build(ans);
return 1;
}
adjlist.assign(n+1, vector<int>());
bool is=false;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(p[i][j] && i!=j){
adjlist[i].push_back(j);
adjlist[j].push_back(i);
}
if(p[i][j]==2)
is=true;
}
}
for(int i=0; i<n; i++){
if(visited[i]==0){
dfs(i);
coun++;
}
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(visited[i]==visited[j] && p[i][j]==0)
return 0;
}
}
vector<vector<int> > answer;
answer.assign(n, vector<int>());
for(int i=0; i<n; i++)
answer[i].assign(n, 0);
map<int, vector<int> > mp;
for(int i=0; i<n; i++)
mp[visited[i]].push_back(i);
for(auto x:mp){
for(int i=1; i<x.s.size(); i++){
answer[x.s[i-1]][x.s[i]]=1;
answer[x.s[i]][x.s[i-1]]=1;
}
if(is){
if(x.s.size()==1)
continue;
if(x.s.size()==2)
return 0;
answer[x.s[0]][x.s[x.s.size()-1]]=1;
answer[x.s[x.s.size()-1]][x.s[0]]=1;
}
}
build(answer);
return 1;
}
Compilation message
supertrees.cpp: In function 'void dfs(int)':
supertrees.cpp:10:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for(int i=0; i<adjlist[s].size(); i++){
| ~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 1; i < div.size(); ++i)
| ~~^~~~~~~~~~~~
supertrees.cpp:90:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 1; i < vv.size(); ++i)
| ~~^~~~~~~~~~~
supertrees.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i=1; i<x.s.size(); i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
10 ms |
1192 KB |
Output is correct |
7 |
Correct |
244 ms |
22028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
10 ms |
1192 KB |
Output is correct |
7 |
Correct |
244 ms |
22028 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
14 ms |
1204 KB |
Output is correct |
13 |
Correct |
261 ms |
22144 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
132 ms |
12044 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
61 ms |
5680 KB |
Output is correct |
21 |
Correct |
248 ms |
22012 KB |
Output is correct |
22 |
Correct |
233 ms |
21956 KB |
Output is correct |
23 |
Correct |
233 ms |
21956 KB |
Output is correct |
24 |
Correct |
238 ms |
22012 KB |
Output is correct |
25 |
Correct |
97 ms |
12028 KB |
Output is correct |
26 |
Correct |
95 ms |
12028 KB |
Output is correct |
27 |
Correct |
247 ms |
22028 KB |
Output is correct |
28 |
Correct |
231 ms |
22016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
14 ms |
1148 KB |
Output is correct |
9 |
Correct |
228 ms |
22140 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
15 ms |
1608 KB |
Output is correct |
13 |
Correct |
267 ms |
30212 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
844 KB |
Output is correct |
17 |
Correct |
125 ms |
13824 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
58 ms |
5756 KB |
Output is correct |
22 |
Correct |
239 ms |
23052 KB |
Output is correct |
23 |
Correct |
230 ms |
22044 KB |
Output is correct |
24 |
Correct |
277 ms |
28404 KB |
Output is correct |
25 |
Correct |
103 ms |
12160 KB |
Output is correct |
26 |
Correct |
105 ms |
9212 KB |
Output is correct |
27 |
Correct |
231 ms |
22148 KB |
Output is correct |
28 |
Correct |
248 ms |
26136 KB |
Output is correct |
29 |
Correct |
105 ms |
12172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
58 ms |
5764 KB |
Output is correct |
5 |
Correct |
254 ms |
22000 KB |
Output is correct |
6 |
Correct |
242 ms |
22032 KB |
Output is correct |
7 |
Correct |
238 ms |
22152 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
74 ms |
5828 KB |
Output is correct |
10 |
Correct |
244 ms |
23096 KB |
Output is correct |
11 |
Correct |
239 ms |
22140 KB |
Output is correct |
12 |
Correct |
250 ms |
28248 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
58 ms |
6236 KB |
Output is correct |
17 |
Correct |
233 ms |
25108 KB |
Output is correct |
18 |
Correct |
288 ms |
23896 KB |
Output is correct |
19 |
Correct |
225 ms |
24004 KB |
Output is correct |
20 |
Correct |
239 ms |
23916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
10 ms |
1192 KB |
Output is correct |
7 |
Correct |
244 ms |
22028 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
14 ms |
1204 KB |
Output is correct |
13 |
Correct |
261 ms |
22144 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
132 ms |
12044 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
61 ms |
5680 KB |
Output is correct |
21 |
Correct |
248 ms |
22012 KB |
Output is correct |
22 |
Correct |
233 ms |
21956 KB |
Output is correct |
23 |
Correct |
233 ms |
21956 KB |
Output is correct |
24 |
Correct |
238 ms |
22012 KB |
Output is correct |
25 |
Correct |
97 ms |
12028 KB |
Output is correct |
26 |
Correct |
95 ms |
12028 KB |
Output is correct |
27 |
Correct |
247 ms |
22028 KB |
Output is correct |
28 |
Correct |
231 ms |
22016 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
14 ms |
1148 KB |
Output is correct |
37 |
Correct |
228 ms |
22140 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
15 ms |
1608 KB |
Output is correct |
41 |
Correct |
267 ms |
30212 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
5 ms |
844 KB |
Output is correct |
45 |
Correct |
125 ms |
13824 KB |
Output is correct |
46 |
Correct |
1 ms |
204 KB |
Output is correct |
47 |
Correct |
1 ms |
204 KB |
Output is correct |
48 |
Correct |
0 ms |
204 KB |
Output is correct |
49 |
Correct |
58 ms |
5756 KB |
Output is correct |
50 |
Correct |
239 ms |
23052 KB |
Output is correct |
51 |
Correct |
230 ms |
22044 KB |
Output is correct |
52 |
Correct |
277 ms |
28404 KB |
Output is correct |
53 |
Correct |
103 ms |
12160 KB |
Output is correct |
54 |
Correct |
105 ms |
9212 KB |
Output is correct |
55 |
Correct |
231 ms |
22148 KB |
Output is correct |
56 |
Correct |
248 ms |
26136 KB |
Output is correct |
57 |
Correct |
105 ms |
12172 KB |
Output is correct |
58 |
Correct |
0 ms |
204 KB |
Output is correct |
59 |
Correct |
0 ms |
204 KB |
Output is correct |
60 |
Correct |
5 ms |
716 KB |
Output is correct |
61 |
Correct |
116 ms |
12044 KB |
Output is correct |
62 |
Correct |
0 ms |
204 KB |
Output is correct |
63 |
Correct |
1 ms |
204 KB |
Output is correct |
64 |
Correct |
1 ms |
204 KB |
Output is correct |
65 |
Correct |
62 ms |
6244 KB |
Output is correct |
66 |
Correct |
118 ms |
14064 KB |
Output is correct |
67 |
Correct |
150 ms |
14072 KB |
Output is correct |
68 |
Correct |
100 ms |
14060 KB |
Output is correct |
69 |
Incorrect |
230 ms |
23932 KB |
Answer gives possible 1 while actual possible 0 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
10 ms |
1192 KB |
Output is correct |
7 |
Correct |
244 ms |
22028 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
14 ms |
1204 KB |
Output is correct |
13 |
Correct |
261 ms |
22144 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
5 ms |
716 KB |
Output is correct |
17 |
Correct |
132 ms |
12044 KB |
Output is correct |
18 |
Correct |
0 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
61 ms |
5680 KB |
Output is correct |
21 |
Correct |
248 ms |
22012 KB |
Output is correct |
22 |
Correct |
233 ms |
21956 KB |
Output is correct |
23 |
Correct |
233 ms |
21956 KB |
Output is correct |
24 |
Correct |
238 ms |
22012 KB |
Output is correct |
25 |
Correct |
97 ms |
12028 KB |
Output is correct |
26 |
Correct |
95 ms |
12028 KB |
Output is correct |
27 |
Correct |
247 ms |
22028 KB |
Output is correct |
28 |
Correct |
231 ms |
22016 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
204 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Correct |
1 ms |
256 KB |
Output is correct |
34 |
Correct |
0 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
14 ms |
1148 KB |
Output is correct |
37 |
Correct |
228 ms |
22140 KB |
Output is correct |
38 |
Correct |
0 ms |
204 KB |
Output is correct |
39 |
Correct |
0 ms |
204 KB |
Output is correct |
40 |
Correct |
15 ms |
1608 KB |
Output is correct |
41 |
Correct |
267 ms |
30212 KB |
Output is correct |
42 |
Correct |
1 ms |
204 KB |
Output is correct |
43 |
Correct |
1 ms |
204 KB |
Output is correct |
44 |
Correct |
5 ms |
844 KB |
Output is correct |
45 |
Correct |
125 ms |
13824 KB |
Output is correct |
46 |
Correct |
1 ms |
204 KB |
Output is correct |
47 |
Correct |
1 ms |
204 KB |
Output is correct |
48 |
Correct |
0 ms |
204 KB |
Output is correct |
49 |
Correct |
58 ms |
5756 KB |
Output is correct |
50 |
Correct |
239 ms |
23052 KB |
Output is correct |
51 |
Correct |
230 ms |
22044 KB |
Output is correct |
52 |
Correct |
277 ms |
28404 KB |
Output is correct |
53 |
Correct |
103 ms |
12160 KB |
Output is correct |
54 |
Correct |
105 ms |
9212 KB |
Output is correct |
55 |
Correct |
231 ms |
22148 KB |
Output is correct |
56 |
Correct |
248 ms |
26136 KB |
Output is correct |
57 |
Correct |
105 ms |
12172 KB |
Output is correct |
58 |
Correct |
0 ms |
204 KB |
Output is correct |
59 |
Correct |
0 ms |
204 KB |
Output is correct |
60 |
Correct |
0 ms |
204 KB |
Output is correct |
61 |
Correct |
58 ms |
5764 KB |
Output is correct |
62 |
Correct |
254 ms |
22000 KB |
Output is correct |
63 |
Correct |
242 ms |
22032 KB |
Output is correct |
64 |
Correct |
238 ms |
22152 KB |
Output is correct |
65 |
Correct |
1 ms |
204 KB |
Output is correct |
66 |
Correct |
74 ms |
5828 KB |
Output is correct |
67 |
Correct |
244 ms |
23096 KB |
Output is correct |
68 |
Correct |
239 ms |
22140 KB |
Output is correct |
69 |
Correct |
250 ms |
28248 KB |
Output is correct |
70 |
Correct |
0 ms |
204 KB |
Output is correct |
71 |
Correct |
0 ms |
204 KB |
Output is correct |
72 |
Correct |
0 ms |
204 KB |
Output is correct |
73 |
Correct |
58 ms |
6236 KB |
Output is correct |
74 |
Correct |
233 ms |
25108 KB |
Output is correct |
75 |
Correct |
288 ms |
23896 KB |
Output is correct |
76 |
Correct |
225 ms |
24004 KB |
Output is correct |
77 |
Correct |
239 ms |
23916 KB |
Output is correct |
78 |
Correct |
0 ms |
204 KB |
Output is correct |
79 |
Correct |
0 ms |
204 KB |
Output is correct |
80 |
Correct |
5 ms |
716 KB |
Output is correct |
81 |
Correct |
116 ms |
12044 KB |
Output is correct |
82 |
Correct |
0 ms |
204 KB |
Output is correct |
83 |
Correct |
1 ms |
204 KB |
Output is correct |
84 |
Correct |
1 ms |
204 KB |
Output is correct |
85 |
Correct |
62 ms |
6244 KB |
Output is correct |
86 |
Correct |
118 ms |
14064 KB |
Output is correct |
87 |
Correct |
150 ms |
14072 KB |
Output is correct |
88 |
Correct |
100 ms |
14060 KB |
Output is correct |
89 |
Incorrect |
230 ms |
23932 KB |
Answer gives possible 1 while actual possible 0 |