This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
struct dsu {
vector<int> p;
vector<vector<int>> v;
void init(int n) {
p.resize(n);
v.resize(n);
for(int i = 0;i < n;i++) {
p[ i ] = i;
v[ i ].push_back({ i });
}
}
int find(int x) {
return p[ x ] = (p[ x ] == x ? p[ x ] : find(p[ x ]));
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(v[ a ].size() < v[ b ].size()) swap(a, b);
for(int i = 0;i < v[ b ].size();i++)
v[ a ].push_back(v[ b ][ i ]);
p[ b ] = a;
}
};
const int N = 1000;
vector<vector<int>> rs;
vector<int> g[ N ];
int rt;
bool visited[ N ];
int dfs(int s, int rt) {
visited[ s ] = 1;
for(int c : g[ s ]) {
if(visited[ c ])
continue;
rs[ s ][ c ] = 1;
rs[ c ][ s ] = 1;
return dfs(c, rt) + 1;
}
if(s != rt) {
rs[ s ][ rt ] = 1;
rs[ rt ][ s ] = 1;
}
return 1;
}
// void build(vector<vector<int>> p) {
// for(auto c : p) {
// for(int x : c) cout << x << ' ';
// cout << '\n';
// }
// }
int construct(vector<vector<int>> p) {
int n = p.size();
dsu ds;
dsu ds0;
ds.init(n);
ds0.init(n);
rs.resize(n, vector<int>(n));
vector<pair<int, int>> e[3];
for(int i = 0;i < n;i++) {
for(int j = i + 1;j < n;j++) {
if(p[ i ][ j ] == 3)
return 0;
if(p[ i ][ j ]) {
ds0.unite(i, j);
if(p[ i ][ j ] == 1)
ds.unite(i, j);
}
e[p[ i ][ j ]].push_back({i, j});
}
}
for(pair<int, int> c : e[ 0 ])
if(ds0.find(c.first) == ds0.find(c.second))
return 0;
for(pair<int, int> c : e[ 2 ])
if(ds.find(c.first) == ds.find(c.second))
return 0;
else {
g[ ds.find(c.first) ].push_back(ds.find(c.second));
g[ ds.find(c.second) ].push_back(ds.find(c.first));
}
for(int i = 0;i < n;i++) {
if(visited[ i ]) continue;
if(dfs(i, i) == 2) return 0;
}
bool us[ n ] = {};
for(int i = 0;i < n;i++) {
if(us[ i ]) continue;
int x = ds.find(i);
for(int to : ds.v[ x ]) {
if(to == x) continue;
us[ to ] = 1;
rs[ x ][ to ] = 1;
rs[ to ][ x ] = 1;
}
}
build(rs);
return 1;
}
// int main() {
// int n;
// cin >> n;
// vector<vector<int>> p(n, vector<int>(n));
// for(int i = 0;i < n;i++) {
// for(int j = 0;j < n;j++) {
// cin >> p[i][j];
// }
// }
// cout << construct(p);
// }
Compilation message (stderr)
supertrees.cpp: In member function 'void dsu::unite(int, int)':
supertrees.cpp:25:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int i = 0;i < v[ b ].size();i++)
| ~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |