#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
class DSU {
vector<int> par;
vector<int> siz;
public:
DSU(int n) {
par.resize(n);
iota(par.begin(),par.end(),0);
siz.assign(n,1);
}
int find_set(int u) {
if (par[u]==u) return u;
return par[u]=find_set(par[u]);
}
bool is_same(int u, int v) {
return find_set(u)==find_set(v);
}
bool unite_set(int u, int v) {
u=find_set(u);
v=find_set(v);
if (u==v) return false;
if (siz[u]<siz[v]) swap(u,v);
par[v]=u;
siz[u]+=siz[v];
return true;
}
};
int construct(vector<vector<int>> p) {
int n = p.size();
vector<vector<int>> ans(n,vector<int>(n,0));
DSU dsu1=DSU(n);
DSU dsu2=DSU(n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (i==j) continue;
if (p[i][j]==1) {
dsu1.unite_set(i,j);
}
if (p[i][j]==2) {
dsu2.unite_set(i,j);
}
}
}
// for (int i=0; i<n; i++) {
// for (int j=0; j<n; j++) {
// if (p[i][j]==0&&(dsu1.is_same(i,j)||dsu2.is_same(i,j))) {
// return 0;
// }
// if (p[i][j]==1) {
// if (dsu2.is_same(i,j)) return 0;
// }
// if (p[i][j]==2) {
// if (dsu1.is_same(i,j)) return 0;
// }
// }
// }
unordered_map<int,vector<int>> m1, m2;
for (int i=0; i<n; i++) {
int s2=dsu2.find_set(i);
int s1=dsu1.find_set(i);
if (s1==i) {
if (find(m2[s2].begin(),m2[s2].end(),i)==m2[s2].end()) {
m2[s2].push_back(i);
}
} else {
if (find(m2[s2].begin(),m2[s2].end(),s1)==m2[s2].end()) {
m2[s2].push_back(s1);
}
if (find(m1[s1].begin(),m1[s1].end(),i)==m1[s1].end()) {
m1[s1].push_back(i);
}
}
}
for (auto i: m2) {
vector<int> s=i.second;
if (s.size()==1) continue;
ans[s.front()][s.back()]=1;
ans[s.back()][s.front()]=1;
for (int j=0; j<s.size()-1; j++) {
ans[s[j]][s[j+1]]=1;
ans[s[j+1]][s[j]]=1;
}
for (int j=0; j<s.size(); j++) {
if (m1.count(s[j])) {
vector<int> s2=m1[s[j]];
for (int k: s2) {
if (k!=s[j]) {
ans[k][s[j]]=1;
ans[s[j]][k]=1;
}
}
}
}
}
build(ans);
return 1;
}
Compilation message
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:87:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int j=0; j<s.size()-1; j++) {
| ~^~~~~~~~~~~
supertrees.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for (int j=0; j<s.size(); j++) {
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
1 ms |
504 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Answer gives possible 1 while actual possible 0 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Too few ways to get from 1 to 2, should be 1 found 0 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
600 KB |
Too few ways to get from 0 to 1, should be 1 found 0 |
| 3 |
Halted |
0 ms |
0 KB |
- |
