#include<bits/stdc++.h>
#include "supertrees.h"
#define MAXN 300007
using namespace std;
int n;
int dsu[MAXN],dsu2[MAXN];
vector<int> comp[MAXN],comp2[MAXN];
vector< vector<int> > ans;
int root(int x){
if(dsu[x]==x)return x;
dsu[x]=root(dsu[x]);
return dsu[x];
}
void mergev(int x,int y){
dsu[root(x)]=root(y);
}
int root2(int x){
if(dsu2[x]==x)return x;
dsu2[x]=root2(dsu2[x]);
return dsu2[x];
}
void mergev2(int x,int y){
dsu2[root2(x)]=root2(y);
}
void add_edge(int x,int y){
ans[x][y]=ans[y][x]=1;
}
int construct(vector< vector<int> > p){
n=int(p.size());
ans.resize(n);
for(int i=0;i<n;i++){
ans[i].resize(n);
}
for(int i=0;i<n;i++){
dsu[i]=dsu2[i]=i;
}
for(int i=0;i<n;i++){
for(int f=i+1;f<n;f++){
if(p[i][f]==1)mergev(i,f);
}
}
for(int i=0;i<n;i++){
comp[root(i)].push_back(i);
}
for(int i=0;i<n;i++){
if(comp[i].empty())continue;
for(int f=0;f<comp[i].size();f++){
for(int k=f+1;k<comp[i].size();k++){
if(p[comp[i][f]][comp[i][k]]!=1)return 0;
}
}
for(int f=0;f<comp[i].size()-1;f++){
add_edge(comp[i][f],comp[i][f+1]);
}
}
for(int i=0;i<n;i++){
for(int f=i+1;f<n;f++){
if(p[i][f]==2)mergev2(root(i),root(f));
}
}
for(int i=0;i<n;i++){
if(comp[i].empty())continue;
comp2[root2(i)].push_back(i);
}
for(int i=0;i<n;i++){
if(comp2[i].empty() or comp2[i].size()==1)continue;
for(int f=0;f<comp2[i].size();f++){
for(int k=f+1;k<comp2[i].size();k++){
for(int t:comp[comp2[i][f]]){
for(int s:comp[comp2[i][k]]){
if(p[t][s]!=2)return 0;
}
}
}
}
for(int f=0;f<comp2[i].size();f++){
add_edge(comp2[i][f],comp2[i][(f+1)%int(comp2[i].size())]);
}
}
for(int i=0;i<n;i++){
for(int f=i+1;f<n;f++){
if(root2(root(i))!=root2(root(f)) and p[i][f]!=0)return 0;
}
}
build(ans);
/*
for(int i=0;i<ans.size();i++){
for(int f=0;f<ans.size();f++){
cout<<ans[i][f]<<" ";
}
cout<<"\n";
}
*/
return 1;
}
/*
int main(){
construct({{1, 1, 1,1}, {1, 1, 1,1}, {1,1,1,1}, {1,1,1,1}});
}
*/
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int f=0;f<comp[i].size();f++){
| ~^~~~~~~~~~~~~~~
supertrees.cpp:61:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int k=f+1;k<comp[i].size();k++){
| ~^~~~~~~~~~~~~~~
supertrees.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int f=0;f<comp[i].size()-1;f++){
| ~^~~~~~~~~~~~~~~~~
supertrees.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int f=0;f<comp2[i].size();f++){
| ~^~~~~~~~~~~~~~~~
supertrees.cpp:85:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int k=f+1;k<comp2[i].size();k++){
| ~^~~~~~~~~~~~~~~~
supertrees.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int f=0;f<comp2[i].size();f++){
| ~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14400 KB |
Output is correct |
2 |
Correct |
7 ms |
14396 KB |
Output is correct |
3 |
Correct |
7 ms |
14340 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14292 KB |
Output is correct |
6 |
Correct |
13 ms |
15256 KB |
Output is correct |
7 |
Correct |
170 ms |
36424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14400 KB |
Output is correct |
2 |
Correct |
7 ms |
14396 KB |
Output is correct |
3 |
Correct |
7 ms |
14340 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14292 KB |
Output is correct |
6 |
Correct |
13 ms |
15256 KB |
Output is correct |
7 |
Correct |
170 ms |
36424 KB |
Output is correct |
8 |
Correct |
8 ms |
14292 KB |
Output is correct |
9 |
Correct |
8 ms |
14292 KB |
Output is correct |
10 |
Correct |
6 ms |
14292 KB |
Output is correct |
11 |
Correct |
8 ms |
14292 KB |
Output is correct |
12 |
Correct |
14 ms |
15312 KB |
Output is correct |
13 |
Correct |
166 ms |
36472 KB |
Output is correct |
14 |
Correct |
8 ms |
14392 KB |
Output is correct |
15 |
Correct |
8 ms |
14312 KB |
Output is correct |
16 |
Correct |
12 ms |
14892 KB |
Output is correct |
17 |
Correct |
81 ms |
26444 KB |
Output is correct |
18 |
Correct |
8 ms |
14292 KB |
Output is correct |
19 |
Correct |
7 ms |
14292 KB |
Output is correct |
20 |
Correct |
45 ms |
20004 KB |
Output is correct |
21 |
Correct |
169 ms |
36332 KB |
Output is correct |
22 |
Correct |
172 ms |
36396 KB |
Output is correct |
23 |
Correct |
172 ms |
36308 KB |
Output is correct |
24 |
Correct |
163 ms |
36428 KB |
Output is correct |
25 |
Correct |
74 ms |
26412 KB |
Output is correct |
26 |
Correct |
71 ms |
26492 KB |
Output is correct |
27 |
Correct |
172 ms |
36376 KB |
Output is correct |
28 |
Correct |
160 ms |
36412 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
14292 KB |
Output is correct |
2 |
Correct |
6 ms |
14400 KB |
Output is correct |
3 |
Correct |
9 ms |
14400 KB |
Output is correct |
4 |
Incorrect |
6 ms |
14292 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
7 ms |
14292 KB |
Output is correct |
3 |
Correct |
7 ms |
14292 KB |
Output is correct |
4 |
Correct |
51 ms |
19964 KB |
Output is correct |
5 |
Correct |
162 ms |
36320 KB |
Output is correct |
6 |
Correct |
162 ms |
36336 KB |
Output is correct |
7 |
Correct |
171 ms |
36320 KB |
Output is correct |
8 |
Correct |
7 ms |
14308 KB |
Output is correct |
9 |
Correct |
46 ms |
20044 KB |
Output is correct |
10 |
Correct |
164 ms |
36404 KB |
Output is correct |
11 |
Correct |
168 ms |
36416 KB |
Output is correct |
12 |
Correct |
170 ms |
36408 KB |
Output is correct |
13 |
Correct |
9 ms |
14404 KB |
Output is correct |
14 |
Correct |
7 ms |
14292 KB |
Output is correct |
15 |
Correct |
7 ms |
14292 KB |
Output is correct |
16 |
Correct |
45 ms |
19960 KB |
Output is correct |
17 |
Correct |
163 ms |
36440 KB |
Output is correct |
18 |
Correct |
168 ms |
36404 KB |
Output is correct |
19 |
Correct |
164 ms |
36428 KB |
Output is correct |
20 |
Correct |
166 ms |
36464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14400 KB |
Output is correct |
2 |
Correct |
7 ms |
14396 KB |
Output is correct |
3 |
Correct |
7 ms |
14340 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14292 KB |
Output is correct |
6 |
Correct |
13 ms |
15256 KB |
Output is correct |
7 |
Correct |
170 ms |
36424 KB |
Output is correct |
8 |
Correct |
8 ms |
14292 KB |
Output is correct |
9 |
Correct |
8 ms |
14292 KB |
Output is correct |
10 |
Correct |
6 ms |
14292 KB |
Output is correct |
11 |
Correct |
8 ms |
14292 KB |
Output is correct |
12 |
Correct |
14 ms |
15312 KB |
Output is correct |
13 |
Correct |
166 ms |
36472 KB |
Output is correct |
14 |
Correct |
8 ms |
14392 KB |
Output is correct |
15 |
Correct |
8 ms |
14312 KB |
Output is correct |
16 |
Correct |
12 ms |
14892 KB |
Output is correct |
17 |
Correct |
81 ms |
26444 KB |
Output is correct |
18 |
Correct |
8 ms |
14292 KB |
Output is correct |
19 |
Correct |
7 ms |
14292 KB |
Output is correct |
20 |
Correct |
45 ms |
20004 KB |
Output is correct |
21 |
Correct |
169 ms |
36332 KB |
Output is correct |
22 |
Correct |
172 ms |
36396 KB |
Output is correct |
23 |
Correct |
172 ms |
36308 KB |
Output is correct |
24 |
Correct |
163 ms |
36428 KB |
Output is correct |
25 |
Correct |
74 ms |
26412 KB |
Output is correct |
26 |
Correct |
71 ms |
26492 KB |
Output is correct |
27 |
Correct |
172 ms |
36376 KB |
Output is correct |
28 |
Correct |
160 ms |
36412 KB |
Output is correct |
29 |
Correct |
8 ms |
14292 KB |
Output is correct |
30 |
Correct |
6 ms |
14400 KB |
Output is correct |
31 |
Correct |
9 ms |
14400 KB |
Output is correct |
32 |
Incorrect |
6 ms |
14292 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14400 KB |
Output is correct |
2 |
Correct |
7 ms |
14396 KB |
Output is correct |
3 |
Correct |
7 ms |
14340 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
7 ms |
14292 KB |
Output is correct |
6 |
Correct |
13 ms |
15256 KB |
Output is correct |
7 |
Correct |
170 ms |
36424 KB |
Output is correct |
8 |
Correct |
8 ms |
14292 KB |
Output is correct |
9 |
Correct |
8 ms |
14292 KB |
Output is correct |
10 |
Correct |
6 ms |
14292 KB |
Output is correct |
11 |
Correct |
8 ms |
14292 KB |
Output is correct |
12 |
Correct |
14 ms |
15312 KB |
Output is correct |
13 |
Correct |
166 ms |
36472 KB |
Output is correct |
14 |
Correct |
8 ms |
14392 KB |
Output is correct |
15 |
Correct |
8 ms |
14312 KB |
Output is correct |
16 |
Correct |
12 ms |
14892 KB |
Output is correct |
17 |
Correct |
81 ms |
26444 KB |
Output is correct |
18 |
Correct |
8 ms |
14292 KB |
Output is correct |
19 |
Correct |
7 ms |
14292 KB |
Output is correct |
20 |
Correct |
45 ms |
20004 KB |
Output is correct |
21 |
Correct |
169 ms |
36332 KB |
Output is correct |
22 |
Correct |
172 ms |
36396 KB |
Output is correct |
23 |
Correct |
172 ms |
36308 KB |
Output is correct |
24 |
Correct |
163 ms |
36428 KB |
Output is correct |
25 |
Correct |
74 ms |
26412 KB |
Output is correct |
26 |
Correct |
71 ms |
26492 KB |
Output is correct |
27 |
Correct |
172 ms |
36376 KB |
Output is correct |
28 |
Correct |
160 ms |
36412 KB |
Output is correct |
29 |
Correct |
8 ms |
14292 KB |
Output is correct |
30 |
Correct |
6 ms |
14400 KB |
Output is correct |
31 |
Correct |
9 ms |
14400 KB |
Output is correct |
32 |
Incorrect |
6 ms |
14292 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |