제출 #703849

#제출 시각아이디문제언어결과실행 시간메모리
703849bebra슈퍼트리 잇기 (IOI20_supertrees)C++17
40 / 100
260 ms22284 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; 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) { int m = comp.size(); if (m == 1) continue; map<int, int> color; 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; } if (p[u][v] == 1) { color[u] = 1; color[v] = 1; } if (p[u][v] == 2) { if (color[u] != 1) { color[u] = 2; } if (color[v] != 1) { color[v] = 2; } } } } vector<int> line; int cnt1 = 0; for (const auto& [v, col] : color) { if (col == 1) { ++cnt1; line.push_back(v); } } int cnt2 = 0; for (const auto& [v, col] : color) { if (col == 2) { ++cnt2; line.push_back(v); } } if (cnt1 == 0 && cnt2 == 2) { ok = false; break; } // if (cnt1 > 0 && cnt2 == 1) { // ok = false; // break; // } // if (cnt1 + cnt2 != m) { // ok = false; // break; // } for (int i = 0; i < m - 1; ++i) { g[line[i]][line[i + 1]] = 1; g[line[i + 1]][line[i]] = 1; } if (cnt2 == 0) continue; if (cnt1 == 0) { g[line[0]][line.back()] = g[line.back()][line[0]] = 1; } else { g[line[cnt1 - 1]][line.back()] = g[line.back()][line[cnt1 - 1]] = 1; } } // dbg(ok); // for (int i = 0; i < n; ++i) { // for (int j = 0; j < n; ++j) { // if (g[i][j] == 1) { // cout << i + 1 << ' ' << j + 1 << '\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...