Submission #777817

#TimeUsernameProblemLanguageResultExecution timeMemory
777817Minindu206Connecting Supertrees (IOI20_supertrees)C++14
100 / 100
176 ms22164 KiB
#include "supertrees.h" #include <vector> #include <bits/stdc++.h> using namespace std; struct DSU { int n; vector<int> par, sz; void init(int _n) { n = _n; par.resize(n + 1, -1); sz.resize(n + 1, 0); } int finds(int a) { if (par[a] == -1) return a; return par[a] = finds(par[a]); } void unites(int a, int b) { int x = finds(a); int y = finds(b); if (x != y) { if (sz[x] < sz[y]) swap(x, y); par[y] = x; sz[x] += sz[y]; } } }; int construct(std::vector<std::vector<int>> p) { int n = p.size(); DSU d; d.init(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; if (p[i][j] == 3) return 0; if (p[i][j]) d.unites(i, j); } } map<int, vector<int>> mp; for (int i = 0; i < n; i++) { mp[d.finds(i)].push_back(i); for (int j = 0; j < n; j++) { if (i == j) continue; if (p[i][j] == 0) if (d.finds(i) == d.finds(j)) return 0; } } vector<vector<int>> ans(n, vector<int>(n, 0)); for (auto a : mp) { vector<int> vis(n, 0), cyc; for (auto b : a.second) { if (vis[b]) continue; cyc.push_back(b); vis[b] = 1; for (auto c : a.second) { if (vis[c] == 1) continue; if (p[b][c] == 1) { vis[c] = 1; ans[b][c] = 1; ans[c][b] = 1; } } } if (cyc.size() == 2) return 0; int st = -1; for (auto b : cyc) { if (st == -1) st = b; else { ans[st][b] = 1; ans[b][st] = 1; st = b; } } if (cyc.size() > 2) { ans[st][cyc[0]] = 1; ans[cyc[0]][st] = 1; } } build(ans); 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...