Submission #502984

#TimeUsernameProblemLanguageResultExecution timeMemory
502984sliviuConnecting Supertrees (IOI20_supertrees)C++14
40 / 100
223 ms22168 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; int construct(vector<vector<int>> p) { int n = p.size(), cur = 0, bad = 0, sp = 0; vector<vector<int>> ans(n, vector<int>(n)); vector<int> seen(n), solved(n), cycle; function<void(int)> dfs = [&](int node) { if (bad) return; seen[node] = cur; int c1 = 0, c2 = 0; for (int i = 0; i < n; ++i) if (i != node) { if (p[node][i] == 1) ++c1; else if (p[node][i] == 2) ++c2; else if (p[node][i] == 3) bad = 1; if (!seen[i] && p[node][i]) dfs(i); if (!p[node][i] && seen[i] == cur) bad = 1; } if (!c1 && c2) cycle.emplace_back(node); if (c1 && c2) ++sp, cycle.emplace_back(node); if (!solved[node] && c1) { solved[node] = 1; int cur = node; for (int i = 0; i < n; ++i) if (i != node && p[node][i] == 1) ans[cur][i] = ans[i][cur] = solved[i] = 1, cur = i; } }; for (int i = 0; i < n; ++i) if (!seen[i]) { cycle.clear(); ++cur; sp = 0; dfs(i); if (bad) return 0; if (!cycle.empty()) { if (cycle.size() + sp == 2) return 0; int cur = i; for (auto x : cycle) if (x != i) { ans[cur][x] = ans[x][cur] = 1; cur = x; } ans[cur][i] = ans[i][cur] = 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...