제출 #703840

#제출 시각아이디문제언어결과실행 시간메모리
703840bebra슈퍼트리 잇기 (IOI20_supertrees)C++17
21 / 100
218 ms24060 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> parent; vector<int> size; DSU(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); size.assign(n, 1); } int find(int v) { if (parent[v] == v) { return v; } else { return parent[v] = find(parent[v]); } } void unite(int u, int v) { if (u == v) return; u = find(u); v = find(v); if (size[u] > size[v]) swap(u, v); parent[u] = v; size[v] += size[u]; } }; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> g(n, vector<int>(n)); // 1) must be transitive: // p[u][w] * p[w][v] = p[v][w] * p[w][u] = p[u][v] = p[v][u], for any u, v, w bool ok = true; DSU dsu(n); for (int u = 0; u < n; ++u) { for (int v = u + 1; v < n; ++v) { if (p[u][v] > 0) { dsu.unite(u, v); } } } map<int, vector<int>> comps; for (int v = 0; v < n; ++v) { comps[dsu.find(v)].push_back(v); } for (const auto& [c, comp] : comps) { bool has_two = false; for (auto u : comp) { for (auto v : comp) { if (p[u][v] == 0) { ok = false; break; } if (p[u][v] == 2) { has_two = true; } } } for (int i = 0; i < (int)comp.size() - 1; ++i) { g[comp[i]][comp[i + 1]] = g[comp[i + 1]][comp[i]] = 1; } if (has_two) { g[comp[0]][comp.back()] = g[comp.back()][comp[0]] = 1; } } if (ok) { build(g); return 1; } return 0; }
#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...