Submission #1238936

#TimeUsernameProblemLanguageResultExecution timeMemory
1238936Joshua_AnderssonConnecting Supertrees (IOI20_supertrees)C++20
100 / 100
117 ms22272 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; //#define int ll //const int inf = 1e18; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> p2; #define rep(i, high) for (int i = 0; i < (high); i++) #define repp(i, lo, high) for (int i = (lo); i < (high); i++) #define repe(i, container) for (auto& i : container) #define sz(x) ((int)(x).size()) #define all(x) begin(x), end(x) #if _LOCAL static int n; static std::vector<std::vector<int>> p; static std::vector<std::vector<int>> b; static bool called = false; #endif #if _LOCAL static void check(bool cond, std::string message) { if (!cond) { printf("%s\n", message.c_str()); fclose(stdout); exit(0); } } #else static void check(bool cond, std::string message); #endif #if _LOCAL void build(std::vector<std::vector<int>> _b) { check(!called, "build is called more than once"); called = true; check((int)_b.size() == n, "Invalid number of rows in b"); for (int i = 0; i < n; i++) { check((int)_b[i].size() == n, "Invalid number of columns in b"); } b = _b; } #else void build(std::vector<std::vector<int>> _b); #endif struct UF { vi par; vi size; UF(int n) : par(n), size(n, 1) { rep(i, n) par[i] = i; } int find(int x) { return par[x] == x ? x: par[x] = find(par[x]); } void merge(int a, int b) { a = find(a); b = find(b); if (a == b) return; par[b] = a; size[a] += size[b]; } }; int construct(vvi p) { int n = p.size(); vvi ans(n,vi(n)); UF uf(n); rep(i, n) rep(j, n) { if (p[i][j]) uf.merge(i, j); if (p[i][j] == 3) return 0; } map<int, vi> comps; rep(i, n) comps[uf.find(i)].push_back(i); repe(c, comps) { vi& comp = c.second; if (sz(comp) == 0) continue; int all_one = 1; repe(a, comp) { repe(b, comp) { all_one &= p[a][b] == 1; if (!p[a][b]) { return 0; } } } if (all_one) { rep(i, sz(comp) - 1) { int u = comp[i]; int v = comp[i + 1]; ans[u][v] = 1; ans[v][u] = 1; } } else { UF uf2(n); repe(a, comp) { repe(b, comp) { //cout << p[a][b] << " "; if (p[a][b] == 1) { uf2.merge(a, b); } } //cout << "\n"; } set<int> cycleset; map<int, vi> heads; repe(a, comp) { if (uf2.find(a) == a) cycleset.insert(a); else { if (!heads.count(uf2.find(a))) cycleset.insert(uf2.find(a)); heads[uf2.find(a)].push_back(a); } } vi cycle(all(cycleset)); if (sz(cycle) <= 2) { return 0; } rep(i, sz(cycle)) { int u = cycle[i]; int v = cycle[(i + 1) % sz(cycle)]; ans[u][v] = 1; ans[v][u] = 1; } repe(g, heads) { int p = g.first; repe(u, g.second) { ans[p][u] = 1; ans[u][p] = 1; p = u; } } } } build(ans); return 1; } #if _LOCAL int main() { ifstream in("e:/in.txt"); cin.rdbuf(in.rdbuf()); cin >> n; p.resize(n); for (int i = 0; i < n; i++) { p[i].resize(n); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> p[i][j]; } } int possible = construct(p); check(possible == 0 || possible == 1, "Invalid return value of construct"); if (possible == 1) { check(called, "construct returned 1 without calling build"); } else { check(!called, "construct called build but returned 0"); } printf("%d\n", possible); if (possible == 1) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j) { printf(" "); } printf("%d", b[i][j]); } printf("\n"); } } fclose(stdout); } #endif
#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...