| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1196140 | noabenysrael | Connecting Supertrees (IOI20_supertrees) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <iostream>
#include <set>
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using pll = pair<int, int>;
using vb = vector<bool>;
using vpll = vector <pll>;
void build(vvll& b);
vvll partition(vll &nums, vvll &p, ll u_bound, ll l_bound) {
vvll part;
ll n = nums.size();
vb vis(n, 0);
for (ll i = 0; i < n; i++) {
if (vis[i]) continue;
part.push_back({ nums[i] });
vis[i] = 1;
for (ll j = i + 1; j < n; j++) {
if (p[nums[i]][nums[j]] >= l_bound && p[nums[i]][nums[j]] <= u_bound) {
vis[j] = true;
part.back().push_back(j);
}
}
}
return part;
}
int construct(std::vector<std::vector<int>> p) {
ll n = p.size();
for (ll i = 0; i < n; i++) {
if (p[i][i] != 1) return 0;
}
for (ll i = 0; i < n; i++) {
for (ll j = i + 1; j < n; j++) {
if (p[i][j] != p[j][i]) return 0;
if (p[i][j] == 3) return 0;
}
}
vll nums(n);
for (ll i = 0; i < n; i++) nums[i] = i;
vvll part1 = partition(nums, p, 2, 1);
vvvll part;
for (vll& v : part1) {
part.push_back(partition(v, p, 1, 1));
}
vpll locs(n);
for (ll comp = 0; comp < part.size(); comp++) {
for (ll tree = 0; tree < part[comp].size(); tree++) {
for (ll v : part[comp][tree]) {
locs[v] = { comp, tree };
}
}
}
for (ll i = 0; i < n; i++) {
for (ll j = i + 1; j < n; j++) {
if (locs[i].first != locs[j].first) {
if (p[i][j] != 0) return 0;
}
else if (locs[i].second == locs[j].second) {
if (p[i][j] != 1) return 0;
}
else if (p[i][j] != 2) return 0;
}
}
vvll b(n, vll(n, 0));
for (vvll& comp : part) {
for (vll& tree : comp) {
for (ll i = 1; i < tree.size(); i++) {
b[tree[i]][tree[0]] = 1;
b[tree[0]][tree[i]] = 1;
}
}
if (comp.size() > 1) {
for (ll i = 0; i < comp.size(); i++) {
b[comp[i][0]][comp[(i + 1) % comp.size()][0]] = 1;
b[comp[(i + 1) % comp.size()][0]][comp[i][0]] = 1;
}
}
}
build(b);
return 1;
}