Submission #1265255

#TimeUsernameProblemLanguageResultExecution timeMemory
1265255canhnam357슈퍼트리 잇기 (IOI20_supertrees)C++20
100 / 100
119 ms22376 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; struct dsu { vector<int> par; vector<vector<int>> cc; dsu(int n) { par.resize(n); cc.resize(n); for (int i = 0; i < n; i++) cc[i].push_back(i); iota(par.begin(), par.end(), 0); } int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); } void join(int a, int b) { a = find(a), b = find(b); if (a != b) { if (cc[a].size() > cc[b].size()) swap(a, b); par[a] = b; for (int i : cc[a]) cc[b].push_back(i); } } }; int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (p[i][j] == 3) return 0; } } dsu e1(n), e(n), e2(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (p[i][j] == 1) e1.join(i, j); if (p[i][j] == 2) e2.join(i, j); if (p[i][j]) e.join(i, j); } } for (int i = 0; i < n; i++) { if (e.par[i] == i) { for (int a : e.cc[i]) { for (int b : e.cc[i]) { if (!p[a][b]) return 0; } } } } for (int i = 0; i < n; i++) { if (e1.par[i] == i) { for (int a : e1.cc[i]) { for (int b : e1.cc[i]) { if (p[a][b] != 1) return 0; } } } } vector<pair<int, int>> edge; for (int i = 0; i < n; i++) { if (e1.par[i] == i) { for (int j = 1; j < e1.cc[i].size(); j++) { edge.emplace_back(e1.cc[i][j - 1], e1.cc[i][j]); } } } for (int i = 0; i < n; i++) { if (e2.par[i] == i) { set<int> s; for (int j : e2.cc[i]) { s.insert(e1.find(j)); } if (s.size() == 2) return 0; if (s.size() == 1) continue; vector<int> v(s.begin(), s.end()); for (int j = 0; j < v.size(); j++) { edge.emplace_back(v[j], v[(j + 1) % v.size()]); } } } vector<vector<int>> res(n, vector<int>(n)); for (auto [u, v] : edge) res[u][v] = res[v][u] = 1; build(res); return 1; } // int main() {}
#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...