#include <bits/stdc++.h>
using namespace std;
class DSU {
public:
DSU(int n) {
m_parent.resize(n);
iota(m_parent.begin(), m_parent.end(), 0);
}
int find(int v) {
if (v == m_parent[v]) {return v;}
int ans = find(m_parent[v]);
m_parent[v] = ans;
return ans;
}
void unionSets(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
m_parent[b] = a;
}
}
private:
vector<int> m_parent;
};
// #define LOCAL
#ifdef LOCAL
void build(vector<vector<int>> p) {
cout << 1 << '\n';
for (auto& row : p) {
for (auto& el : row) cout << el << ' ';
cout << '\n';
}
}
#else
void build(vector<vector<int>> p);
#endif
// p: requirements
// Return
// 0 --> Impossible to construct
// 1 --> Possible and make call to build
int construct(vector<vector<int>> p) {
const int n = p.size();
DSU dsu{n};
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
if (p[i][j]) {
dsu.unionSets(i, j);
}
}
}
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; ++i) {
int repr = dsu.find(i);
groups[repr].push_back(i);
}
vector<vector<int>> answer(n, vector<int>(n,0));
for (auto& [repr, grp] : groups) {
const int m = grp.size();
for (int i = 0; i < m; ++i) {
int s = grp[i];
int e = grp[(i+1)%m];
if (s != e) {
answer[s][e] = 1;
answer[e][s] = 1;
}
}
}
build(answer);
return 1;
}
#ifdef LOCAL
int32_t main(int argc, char** argv) {
assert (argc == 3);
freopen(argv[1], "r", stdin);
freopen(argv[2], "w", stdout);
vector<vector<int>> p;
int n;
cin >> n;
p.resize(n);
for (auto& e : p) {
vector<int> row(n);
for (auto& el : row) cin >> el;
e = row;
}
construct(p);
return 0;
}
#endif
# | 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... |