Submission #1003359

#TimeUsernameProblemLanguageResultExecution timeMemory
1003359toast12Connecting Supertrees (IOI20_supertrees)C++14
11 / 100
125 ms24196 KiB
/* idea for subtask 4: - separate the nodes into different components according to input - in each component, find the nodes that require exactly one path from that node to some other node in the component - create a tree using these nodes - assign one node "root" node and create a cycle with all the 2-path nodes and this node */ #include "supertrees.h" #include <vector> #include <map> #include <iostream> #include <set> using namespace std; #define sz(x) (int)x.size() struct DSU { int n; vector<int> link, size; DSU(int sz) { n = sz; link.resize(sz); size.resize(sz); for (int i = 0; i < n; i++) { link[i] = i; size[i] = 1; } } int find(int x) { while (x != link[x]) x = link[x]; return x; } bool same(int a, int b) { return find(a) == find(b); } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (size[a] < size[b]) swap(a, b); link[b] = a; size[a] += size[b]; } }; int construct(std::vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n)); DSU d(n+1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; if (p[i][j]) { d.unite(i, j); } } } vector<vector<int>> component; vector<bool> done(n); for (int i = 0; i < n; i++) { if (done[i]) continue; int l = d.find(i); vector<int> temp; for (int j = 0; j < n; j++) { if (d.find(j) == l) { done[j] = true; temp.push_back(j); } } if (temp.size() > 1) component.push_back(temp); } for (auto c : component) { if (sz(c) <= 1) continue; DSU dsu(n+1); vector<int> two; set<int> roots; for (int i = 0; i < sz(c); i++) { int r = c[i]; bool o = false; for (int j = 0; j < n; j++) { if (j == r) continue; if (p[r][j] == 1) { o = true; if (dsu.same(r, j)) continue; dsu.unite(r, j); answer[r][j] = 1; answer[j][r] = 1; roots.insert(dsu.find(r)); } } if (!o) two.push_back(r); } if (!two.empty()) { for (auto r : roots) two.push_back(r); for (int i = 0; i < sz(two)-1;i++) { answer[two[i]][two[i+1]] = 1; answer[two[i+1]][two[i]] = 1; } answer[two.back()][two[0]] = 1; answer[two[0]][two.back()] = 1; } } for (int i = 0; i < n; i++) { answer[i][i] = 0; } build(answer); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...