Submission #1195326

#TimeUsernameProblemLanguageResultExecution timeMemory
1195326yoavLConnecting Supertrees (IOI20_supertrees)C++20
100 / 100
119 ms22192 KiB
#include "supertrees.h" #include <bits/stdc++.h> #define rep(i, s, e) for(int i = s; i < e; i++) #define pr(x) cout << x << endl #define wpr(x) cout << #x << "=" << x << endl using namespace std; using vi = vector<int>; using vvi = vector<vi>; using pi = pair<int, int>; using vpi = vector<pi>; using vvpi = vector<vpi>; template<class A> ostream &operator<<(ostream &os, const vector<A> &arr) { if (arr.empty()) { return os << "[]"; } os << "["; rep(i, 0, arr.size()) { os << arr[i] << ",]"[i == arr.size() - 1]; } return os; } template<class A, class B> ostream &operator<<(ostream &os, const pair<A, B> &p) { return os << "{" << p.first << "," << p.second << "}"; } /** * Solution: * 1. First split to C.Cs, and check validity. * 2. For each C.C: * 1. Find cliques of 1's. * 2. Create lines of all of those cliques. * 3. Merge them using a representor to a circle, if there are at least 3 lines. * */ bool handle_comp(vvi &p, vvi &g, vi &comp) { int sz = comp.size(); if (sz == 0) return 1; vi color(sz, -1); int cur_col = 0; vvi cc; rep(i, 0, sz) { if (color[i] >= 0) continue; color[i] = cur_col++; cc.push_back({comp[i]}); rep(j, i+1, sz) { if (p[comp[i]][comp[j]] == 1) { if (color[j] >= 0) return 0; color[j] = color[i]; cc.back().push_back(comp[j]); } } } assert(cur_col <= sz); int valid = 1; rep(i, 0, sz) { rep(j, 0, sz) { int u = comp[i], v = comp[j]; // If they are in the same C.C, p should be 1. Otherwise, 2. if (color[i] == color[j]) { valid &= (p[u][v] == 1); } else { valid &= (p[u][v] == 2); } } } assert(cc.size() > 0); valid &= (cc.size() != 2); if (!valid) return 0; // Create lines: for (auto &line: cc) { rep(i, 1, line.size()) { int u = line[i - 1], v = line[i]; assert(u != v); g[u][v] = g[v][u] = 1; } } if (cc.size() >= 3) { // Merge lines: rep(i, 0, cc.size()) { int nxt = (i + 1) % cc.size(); // assert(cc[i].size() >= 1); // assert(cc[(i + 1) % cc.size()].size() >= 1); int u = cc[nxt][0], v = cc[i][0]; while (u < 0 || u >= g.size()); while (v < 0 || v >= g.size()); g[u][v] = g[v][u] = 1; } } return 1; } int construct(vector<vector<int> > p) { int n = p.size(); rep(i, 0, n) { if (p[i][i] != 1) return 0; // assert(p[i][i] == 1); } vvi g(n, vi(n, 0)); vi color(n, -1); int cur_col = 0; vvi cc; rep(i, 0, n) { if (color[i] >= 0) continue; color[i] = cur_col++; cc.push_back({i}); rep(j, i+1, n) { if (p[i][j] >= 1) { if (color[j] >= 0) return 0; color[j] = color[i]; cc.back().push_back(j); } } } rep(i, 0, n) { rep(j, 0, n) { if ((p[i][j] > 0) ^ (color[i] == color[j])) { return 0; } } } for (auto &comp: cc) { if (!handle_comp(p, g, comp)) return 0; } build(g); return 1; } /* 1 1 2 1 1 1 1 3 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 0 1 0 1 3 1 0 1 0 1 0 1 0 1 3 1 2 2 2 1 2 2 2 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 3 1 2 0 0 1 2 2 0 1 3 1 1 2 2 1 1 2 1 1 5 1 0 2 2 2 0 1 2 2 2 0 2 1 2 2 0 2 2 1 2 0 2 2 2 1 5 1 0 2 1 2 0 1 1 2 2 0 2 1 2 2 0 2 1 1 2 0 2 2 1 1 */
#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...