제출 #502965

#제출 시각아이디문제언어결과실행 시간메모리
502965sliviu슈퍼트리 잇기 (IOI20_supertrees)C++14
21 / 100
214 ms24040 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; 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 (!solved[cur] && c1) { solved[cur] = 1; int cur = node; for (int i = 0; i < n; ++i) if (i != node && p[node][i] == 1) ans[cur][i] = ans[i][cur] = 1, cur = i; } }; for (int i = 0; i < n; ++i) if (!seen[i]) { cycle.clear(); ++cur; dfs(i); if (bad) return 0; if (!cycle.empty()) { 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...