| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1345125 | nanaseyuzuki | 슈퍼트리 잇기 (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include "supertrees.h"
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const int mn = 2e3 + 5, mod = 1e9 + 7, inf = 2e9;
int n, a[mn][mn];
vector <int> comp[mn], all;
struct DSU {
int par[mn], sz[mn];
void init() {
for(int i = 1; i <= n; i++) {
par[i] = i, sz[i] = 1;
}
}
int find(int u) {
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
bool join(int u, int v) {
u = find(u), v = find(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v], par[v] = u;
return true;
}
} Hoa;
int construct(vector <vector<int>> b) {
n = b.size();
vector <vector<int>> ans(n, vector <int> (n));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
a[i][j] = b[i - 1][j - 1];
// cout << a[i][j] << ' ';
}
// cout << '\n';
}
Hoa.init();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(a[i][j] && i != j) {
Hoa.join(i, j);
}
}
}
// check tree structure
// if a[i][j] >= 3 => unlegit since it requires the subgraph has at least 2 bridges => a[i][j] >= 4
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(!a[i][j] && Hoa.find(i) == Hoa.find(j)) return 0;
if(a[i][j] == 3) return 0;
}
}
for(int i = 1; i <= n; i++) {
comp[Hoa.find(i)].push_back(i);
all.push_back(Hoa.find(i));
}
sort(all(all)); all.erase(unique(all(all)), all.end());
for(auto st : all) {
auto &v = comp[st];
int m = v.size();
Hoa.init();
for(int i = 0; i < m; i++) {
for(int j = i + 1; j < m; j++) {
if(a[v[i]][v[j]] == 1 && Hoa.join(v[i], v[j])) {
debug(v[i], v[j]);
ans[v[i] - 1][v[j] - 1] = ans[v[j] - 1][v[i] - 1] = 1;
}
}
}
for(int i = 0; i < m; i++) {
for(int j = i + 1; j < m; j++) {
if(a[v[i]][v[j]] == 2 && Hoa.find(v[i]) == Hoa.find(v[j])) return 0;
}
}
vector <int> parent;
for(auto x : v) parent.push_back({Hoa.find(x)});
sort(all(parent)); parent.erase(unique(all(parent)), parent.end());
for(int i = 0; i < (int) parent.size() - 1; i++) {
int u = parent[i] - 1, v = parent[i + 1] - 1;
ans[u][v] = ans[v][u] = 1;
debug(u + 1, v + 1);
}
if(parent.size() == 1) continue;
if(parent.size() == 2) return 0;
int u = parent.back(), z = parent[0];
ans[u - 1][z - 1] = ans[z - 1][u - 1] = 1;
}
for(int u = 0; u < n; u++) {
for(int v = 0; v < n; v++) {
cout << ans[u][v] << ' ';
}
cout << '\n';
}
// build(ans);
return 1;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
int main() {
ios_base::sync_with_stdio(false);
cout << construct({{1, 0}, {0, 1}}) << '\n';
}