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 "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int p[N];
vector<int> g[N];
int fr(int i) {
return p[i] == i ? i : p[i] = fr(p[i]);
}
int construct(vector<vector<int>> B) {
int n = B.size();
for (int i = 0;i < n;i++) p[i] = i;
vector<vector<int>> ans(n, vector<int>(n, 0));
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
if (B[i][j]) {
p[fr(i)] = fr(j);
}
}
}
for (int i = 0;i < n;i++) {
g[fr(i)].push_back(i);
}
for (int G = 0;G < n;G++) {
if (g[G].empty() || (int)g[G].size() == 1) continue;
auto& v = g[G];
int m = v.size();
int cnt = 0;
for (int i = 0;i < m;i++) {
for (int j = i + 1;j < m;j++) {
if (B[v[i]][v[j]] == 0) return 0;
cnt += (B[v[i]][v[j]] == 1);
}
}
if (cnt == m * (m - 1) / 2) {
for (int i = 1;i < m;i++) {
ans[v[0]][v[i]] = ans[v[i]][v[0]] = 1;
}
}
else {
for (int i = 0;i < m;i++) {
ans[v[i]][v[(i + 1) % m]] = ans[v[(i + 1) % m]][v[i]] = 1;
}
}
}
build(ans);
return 1;
}
# | 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... |