# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
956535 | 2024-04-02T06:50:33 Z | KK_1729 | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; struct UFDS { vector<int> link, siz; UFDS(int n) : link(n), siz(n, 1) { iota(link.begin(), link.end(), 0); } //each element as its own subset, with size 1 int findRoot(int x) { if(x == link[x]) return x; return link[x] = findRoot(link[x]); /* A shorter way of writing the following is: return x == link[x] ? x : link[x] = findRoot(link[x]); */ } bool same(int x, int y) { return findRoot(x) == findRoot(y); } bool unite(int x, int y) { x = findRoot(x); y = findRoot(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; link[y] = x; return true; } int size(int x) { return siz[findRoot(x)]; } }; int construct(std::vector<std::vector<int>> p) { int n = p.size(); std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row; row.resize(n); answer.push_back(row); } UFDS ds(n); for (int i = 0; i < n; ++i){ for (int j = 0; j < n; ++j){ if (p[i][j] == 1) ds.unite(i, j); else{ if (ds.same(i, j)) return 0; } } } vector<vector<int>> parents; for (int i = 0; i < n; ++i) parents[ds.findRoot(i)].pb(i); for (auto item: parents){ int u = item.size(); FOR(i,0,u-1){ answer[item[i]][item[i+1]] = 1; answer[item[i+1]][item[i]] = 1; } } build(answer); return 1; }