# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
301281 | 2020-09-17T19:46:20 Z | Gilgamesh | Connecting Supertrees (IOI20_supertrees) | C++17 | 0 ms | 0 KB |
#include "supertrees.h" #include <vector> const int mxN = 1000; int parent[mxN]; int rank[mxN]; int find(int x) { if(parent[x] == -1) parent[x] = x; if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } bool union(int x, int y) { int xRoot = find(x), yRoot = find(y); if (xRoot == yRoot) return false; if (rank[xRoot] < rank[yRoot]) parent[xRoot] = yRoot; else if (rank[yRoot] < rank[xRoot]) parent[yRoot] = xRoot; else { parent[yRoot] = xRoot; rank[xRoot] = rank[xRoot] + 1; } return true; } 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); } for(int i = 0; i < n; ++i){ parent[i] = i; } for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ if(!p[i][j] && find(i) == find(j)){ return 0; } if(p[i][j]) union(i, j); } } for(int i = 0; i < n; ++i){ int rep = find(i); if(rep == i) continue; answer[rep][i] = 1; answer[i][rep] = 1; } build(answer); return 1; }