Submission #349532

#TimeUsernameProblemLanguageResultExecution timeMemory
349532izhang05Connecting Supertrees (IOI20_supertrees)C++17
21 / 100
267 ms24300 KiB
#include "supertrees.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e3 + 5; int parent[maxn]; vector<int> comp[maxn]; int get(int x) { return parent[x] == x ? x : parent[x] = get(parent[x]); } bool merge(int x, int y) { int xroot = get(x), yroot = get(y); if (comp[xroot].size() < comp[yroot].size()) { swap(xroot, yroot); } if (xroot != yroot) { parent[xroot] = yroot; comp[yroot].insert(comp[yroot].end(), comp[xroot].begin(), comp[xroot].end()); comp[xroot].clear(); return true; } return false; } bool same(int x, int y) { return get(x) == get(y); } int construct(vector<vector<int>> p) { int n = p.size(); for (int i = 0; i < n; ++i) { parent[i] = i; comp[i].push_back(i); if (p[i][i] != 1) { return 0; } } vector<vector<int>> sol(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (p[i][j]) { merge(i, j); } } } for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (!p[i][j] && same(i, j)) { return 0; } } } for (int i = 0; i < n; i++) { if (comp[i].size() > 1) { for (int j = 0; j < (int) comp[i].size() - 1; ++j) { sol[comp[i][j]][comp[i][j + 1]] = 1; sol[comp[i][j + 1]][comp[i][j]] = 1; } if (p[comp[i][0]][comp[i][1]] == 2) { sol[comp[i][0]][comp[i][comp[i].size() - 1]] = 1; sol[comp[i][comp[i].size() - 1]][comp[i][0]] = 1; } } } build(sol); return 1; } #ifdef DEBUG int main() { freopen("1.in", "r", stdin); int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> a[i][j]; } } cout << construct(a) << "\n"; } #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...