#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
int a,c,d,e,i,j,ii,jj,zx,xc,msh1[1009],zm1[1009],msh2[1009],zm2[1009];
int bo[1009],k[1009][1009],cnt;
int B[1009][1009];
vector <int> v[1009],vv[1009];
vector <vector <int> > ans;
int fnd1(int q){
if(msh1[q]==q) return q; else return msh1[q]=fnd1(msh1[q]);
}
void mrg1(int q, int w){
q=fnd1(q);w=fnd1(w);
if(q==w) return;
if(zm1[q]<zm1[w]) swap(q,w);
msh1[w]=q;
if(zm1[q]==zm1[w]) zm1[q]++;
}
int fnd2(int q){
if(msh2[q]==q) return q; else return msh2[q]=fnd2(msh2[q]);
}
void mrg2(int q, int w){
q=fnd2(q);w=fnd2(w);
if(q==w) return;
if(zm2[q]<zm2[w]) swap(q,w);
msh2[w]=q;
if(zm2[q]==zm2[w]) zm2[q]++;
}
void dfs(int q){
bo[q]=cnt;
k[i][q]++;
for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
if(bo[(*it)]==cnt) continue;
dfs((*it));
}
bo[q]=0;
}
int construct(vector <vector <int> > A) {
a = A.size();
for(i=0; i<a; i++){
for(j=0; j<a; j++){
if(A[i][j]==3){
return 0;
}
}
}
for(i=0; i<a; i++){
msh1[i]=i;zm1[i]=1;
}
for(i=0; i<a; i++){
for(j=i+1; j<a; j++){
if(A[i][j]==1){
mrg1(i,j);
}
}
}
for(i=0; i<a; i++){
fnd1(i);
if(i!=msh1[i]){
B[i][msh1[i]]=1;
B[msh1[i]][i]=1;
v[i].push_back(msh1[i]);
v[msh1[i]].push_back(i);
}
}
for(i=0; i<a; i++){
msh2[i]=i;zm2[i]=1;
}
for(i=0; i<a; i++){
for(j=i+1; j<a; j++){
if(A[i][j]==2){
mrg2(msh1[i],msh1[j]);
}
}
}
for(i=0; i<a; i++){
fnd2(i);
vv[msh2[i]].push_back(i);
}
for(i=0; i<a; i++){
if(vv[i].size()>1){
for(j=0; j<vv[i].size(); j++){
jj=j-1;if(jj<0) jj=vv[i].size()-1;
B[vv[i][j]][vv[i][jj]]=1;
B[vv[i][jj]][vv[i][j]]=1;
v[vv[i][j]].push_back(vv[i][jj]);
v[vv[i][jj]].push_back(vv[i][j]);
}
}
}
for(i=0; i<a; i++){
cnt++;
dfs(i);
for(j=0; j<a; j++){
if(k[i][j]!=A[i][j]){
return 0;
}
}
}
for(i=0; i<a; i++){
vector <int> va;
for(j=0; j<a; j++){
va.push_back(B[i][j]);
}
ans.push_back(va);
}
build(ans);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:83:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(j=0; j<vv[i].size(); j++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
12 ms |
2924 KB |
Output is correct |
7 |
Correct |
269 ms |
30188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
12 ms |
2924 KB |
Output is correct |
7 |
Correct |
269 ms |
30188 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
11 ms |
2156 KB |
Output is correct |
13 |
Correct |
266 ms |
26220 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
6 ms |
1516 KB |
Output is correct |
17 |
Correct |
117 ms |
12312 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
67 ms |
9836 KB |
Output is correct |
21 |
Correct |
261 ms |
30104 KB |
Output is correct |
22 |
Correct |
262 ms |
29676 KB |
Output is correct |
23 |
Correct |
273 ms |
30188 KB |
Output is correct |
24 |
Correct |
259 ms |
26348 KB |
Output is correct |
25 |
Correct |
110 ms |
12396 KB |
Output is correct |
26 |
Correct |
105 ms |
11884 KB |
Output is correct |
27 |
Correct |
280 ms |
30188 KB |
Output is correct |
28 |
Correct |
266 ms |
26476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Answer gives possible 1 while actual possible 0 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
67 ms |
9640 KB |
Output is correct |
5 |
Correct |
262 ms |
30188 KB |
Output is correct |
6 |
Correct |
265 ms |
29676 KB |
Output is correct |
7 |
Correct |
273 ms |
30188 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
69 ms |
9708 KB |
Output is correct |
10 |
Correct |
264 ms |
30188 KB |
Output is correct |
11 |
Correct |
264 ms |
30060 KB |
Output is correct |
12 |
Correct |
295 ms |
30188 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
67 ms |
9708 KB |
Output is correct |
17 |
Correct |
261 ms |
30060 KB |
Output is correct |
18 |
Correct |
262 ms |
29804 KB |
Output is correct |
19 |
Correct |
262 ms |
29804 KB |
Output is correct |
20 |
Correct |
269 ms |
26348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
12 ms |
2924 KB |
Output is correct |
7 |
Correct |
269 ms |
30188 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
11 ms |
2156 KB |
Output is correct |
13 |
Correct |
266 ms |
26220 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
6 ms |
1516 KB |
Output is correct |
17 |
Correct |
117 ms |
12312 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
67 ms |
9836 KB |
Output is correct |
21 |
Correct |
261 ms |
30104 KB |
Output is correct |
22 |
Correct |
262 ms |
29676 KB |
Output is correct |
23 |
Correct |
273 ms |
30188 KB |
Output is correct |
24 |
Correct |
259 ms |
26348 KB |
Output is correct |
25 |
Correct |
110 ms |
12396 KB |
Output is correct |
26 |
Correct |
105 ms |
11884 KB |
Output is correct |
27 |
Correct |
280 ms |
30188 KB |
Output is correct |
28 |
Correct |
266 ms |
26476 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Incorrect |
1 ms |
364 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
12 ms |
2924 KB |
Output is correct |
7 |
Correct |
269 ms |
30188 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
11 ms |
2156 KB |
Output is correct |
13 |
Correct |
266 ms |
26220 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
6 ms |
1516 KB |
Output is correct |
17 |
Correct |
117 ms |
12312 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
67 ms |
9836 KB |
Output is correct |
21 |
Correct |
261 ms |
30104 KB |
Output is correct |
22 |
Correct |
262 ms |
29676 KB |
Output is correct |
23 |
Correct |
273 ms |
30188 KB |
Output is correct |
24 |
Correct |
259 ms |
26348 KB |
Output is correct |
25 |
Correct |
110 ms |
12396 KB |
Output is correct |
26 |
Correct |
105 ms |
11884 KB |
Output is correct |
27 |
Correct |
280 ms |
30188 KB |
Output is correct |
28 |
Correct |
266 ms |
26476 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Incorrect |
1 ms |
364 KB |
Answer gives possible 1 while actual possible 0 |
33 |
Halted |
0 ms |
0 KB |
- |