| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288223 | harryleee | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int maxn = 1e3;
struct DSU{
vector<int> par, sz, trace;
int cnt;
inline DSU(int n){
par.resize(n, 0);
sz.resize(n, 1);
for (int i = 0; i < n; ++i) par[i] = i;
trace.resize(n, -1);
cnt = -1;
}
inline int find(int x){
return (par[x] == x) ? x : (par[x] = find(par[x]));
}
inline void merge(int x, int y){
int u = find(x), v = find(y);
if (u == v) return;
if (sz[u] < sz[x]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return;
}
inline int order(int x){
int u = find(x);
if (trace[u] == -1)
trace[u] = ++cnt;
return trace[u];
}
};
int construct(vector<vector<int>> p){
int n = p.size();
vector<vector<int>> vec(n);
vector<vector<bool>> a (n, vector<bool> (n, false));
DSU dsu(n);
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j) if (j != i){
if (p[i][j] != 0) dsu.merge(i, j);
}
}
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j)if (i != j){
if (p[i][j] == 0 && dsu.find(i) == dsu.find(j))
return 0;
}
}
for (int i = 0; i < n; ++i)
vec[dsu.order(i)].push_back(i);
int cnt = dsu.cnt;
for (int k = 0; k < cnt; ++k){
vector<int>& v = vec[k];
if (v.size() > 1 && p[v[0]][v[1]] == 1){
for (int i = 0; i < v.size() - 1; ++i)
a[v[i]][v[i + 1]] = true;
}
if (v.size() > 1 && p[v[0]][v[1]] == 2){
if (v.size() <= 2) return 0;
for (int i = 0; i < v.size() - 1; ++i)
a[v[i]][v[i + 1]] = true;
a[v[v.size() - 1]][v[0]] = true;
}
}
build(res);
return 1;
}