Submission #1057143

#TimeUsernameProblemLanguageResultExecution timeMemory
1057143arbuzickConnecting Supertrees (IOI20_supertrees)C++17
100 / 100
153 ms24188 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; struct DSU { int n; vector<int> sz, p; DSU(int _n) { n = _n; sz.assign(n, 1); p.resize(n); iota(p.begin(), p.end(), 0); } int pr(int v) { if (p[v] == v) { return v; } return p[v] = pr(p[v]); } void unite(int a, int b) { a = pr(a), b = pr(b); if (a == b) { return; } if (sz[a] < sz[b]) { swap(a, b); } p[b] = a; sz[a] += sz[b]; } }; int construct(vector<vector<int>> p) { int n = p.size(); vector<vector<int>> answer(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] == 3) { return 0; } } } DSU d0(n); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] != 0) { d0.unite(i, j); } } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (d0.pr(i) == d0.pr(j) && p[i][j] == 0) { return 0; } } } DSU d1(n); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] == 1) { d1.unite(i, j); } } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (d1.pr(i) == d1.pr(j) && p[i][j] != 1) { return 0; } } if (d1.pr(i) != i) { answer[d1.pr(i)][i] = answer[i][d1.pr(i)] = 1; } } DSU d2(n); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j] == 2) { d2.unite(i, j); } } } vector<vector<int>> cycles(n); for (int i = 0; i < n; ++i) { if (d2.sz[d2.pr(i)] != 1 && i == d1.pr(i)) { cycles[d2.pr(i)].push_back(i); } } for (int i = 0; i < n; ++i) { if (cycles[i].size() == 2) { return 0; } for (int j = 0; j < (int)cycles[i].size(); ++j) { int nxt = j + 1; if (nxt == (int)cycles[i].size()) { nxt = 0; } answer[cycles[i][j]][cycles[i][nxt]] = answer[cycles[i][nxt]][cycles[i][j]] = 1; } } build(answer); return 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...