제출 #703865

#제출 시각아이디문제언어결과실행 시간메모리
703865bebra슈퍼트리 잇기 (IOI20_supertrees)C++17
40 / 100
179 ms22156 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; #define dbg(x) cerr << #x << ": " << x << endl; struct DSU { vector<int> parent; vector<int> size; int comps_n; DSU(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); size.assign(n, 1); comps_n = n; } 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)); 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) { int m = comp.size(); if (m == 1) continue; DSU curr_groups(m); vector<int> cycle; bool has_cycle = false; for (int i = 0; i < m; ++i) { int u = comp[i]; bool has_one = false; for (int j = 0; j < m; ++j) { if (i == j) continue; int v = comp[j]; if (u == v) continue; if (p[u][v] == 0) { ok = false; break; } if (p[u][v] >= 2) { has_cycle = true; } if (p[u][v] == 1) { curr_groups.unite(i, j); has_one = true; } } if (!has_one) { cycle.push_back(u); } } if (!has_cycle) { for (int i = 0; i < m - 1; ++i) { g[comp[i]][comp[i + 1]] = g[comp[i + 1]][comp[i]] = 1; } continue; } map<int, vector<int>> groupsf; for (int i = 0; i < m; ++i) { if (curr_groups.size[curr_groups.find(i)] > 1) { groupsf[curr_groups.find(i)].push_back(comp[i]); } } int groups_n = groupsf.size(); if (groups_n > 2) { ok = false; break; } if (groups_n == 2 && cycle.size() < 1) { ok = false; break; } if (groups_n == 1 && cycle.size() < 2) { ok = false; break; } if (groups_n == 0 && cycle.size() < 3) { ok = false; break; } vector<vector<int>> groups(2); { int i = 0; for (const auto& [f, v] : groupsf) { groups[i] = v; ++i; } } for (int t = 0; t <= 1; ++t) { for (auto u : groups[t]) { for (auto v : groups[t]) { if (p[u][v] != 1) { ok = false; } } } } for (auto u : groups[0]) { for (auto v : groups[1]) { if (p[u][v] != 2) { ok = false; } } } vector<int> line; for (auto v : groups[0]) { line.push_back(v); } for (auto v : cycle) { line.push_back(v); } for (auto v : groups[1]) { line.push_back(v); } if ((int)line.size() != m) { ok = false; break; } for (int i = 0; i < m - 1; ++i) { g[line[i]][line[i + 1]] = g[line[i + 1]][line[i]] = 1; } { int u, v; if (groups_n == 2) { u = groups[0].back(); v = groups[1][0]; } else if (groups_n == 1) { u = groups[0].back(); v = cycle.back(); } else { u = cycle[0]; v = cycle.back(); } g[u][v] = g[v][u] = 1; } } // for (int i = 0; i < n; ++i) { // for (int j = 0; j < n; ++j) { // if (g[i][j] == 1) { // cout << i << ' ' << j << '\n'; // } // } // cout << '\n'; // } if (ok) { build(g); return 1; } return 0; } // int main() { // int n; // cin >> n; // vector<vector<int>> p(n, vector<int>(n)); // for (int i = 0; i < n; ++i) { // for (int j = 0; j < n; ++j) { // cin >> p[i][j]; // } // } // construct(p); // }
#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...