제출 #703897

#제출 시각아이디문제언어결과실행 시간메모리
703897bebra슈퍼트리 잇기 (IOI20_supertrees)C++17
96 / 100
188 ms24012 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) { u = find(u); v = find(v); if (u == v) return; 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); } } } auto add_edge = [&](int u, int v) { g[u][v] = g[v][u] = 1; }; 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]; 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); } } } if (!has_cycle) { for (int i = 0; i < m - 1; ++i) { add_edge(comp[i], 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]); } else { cycle.push_back(comp[i]); } } int groups_n = groupsf.size(); int cycle_size = cycle.size(); for (int i = 0; i < cycle_size - 1; ++i) { add_edge(cycle[i], cycle[i + 1]); } if (groups_n == 0) { if (cycle_size == 2) { ok = false; break; } if (!cycle.empty()) add_edge(cycle[0], cycle.back()); continue; } vector<vector<int>> groups(groups_n); { int i = 0; for (const auto& [f, v] : groupsf) { groups[i] = v; ++i; } } for (int i = 0; i < groups_n; ++i) { int b = groups[i].size(); for (int j = 0; j < b - 1; ++j) { add_edge(groups[i][j], groups[i][j + 1]); } } for (int i = 0; i < groups_n - 1; ++i) { add_edge(groups[i].back(), groups[i + 1].back()); } if (!cycle.empty()) { add_edge(groups[0].back(), cycle[0]); add_edge(groups.back().back(), cycle.back()); } else { add_edge(groups[0].back(), groups.back().back()); } } // 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...