Submission #1211506

#TimeUsernameProblemLanguageResultExecution timeMemory
1211506fafnirConnecting Supertrees (IOI20_supertrees)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; class DSU { public: DSU(int n) { m_parent.resize(n); iota(m_parent.begin(), m_parent.end(), 0); } int find(int v) { if (v == m_parent[v]) {return v;} int ans = find(m_parent[v]); m_parent[v] = ans; return ans; } void unionSets(int a, int b) { a = find(a); b = find(b); if (a != b) { m_parent[b] = a; } } private: vector<int> m_parent; }; // #define LOCAL #ifdef LOCAL void build(vector<vector<int>> p) { cout << 1 << '\n'; for (auto& row : p) { for (auto& el : row) cout << el << ' '; cout << '\n'; } } #else void build(vector<vector<int>> p); #endif // p: requirements // Return // 0 --> Impossible to construct // 1 --> Possible and make call to build int construct(vector<vector<int>> p) { const int n = p.size(); DSU dsu{n}; for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { if (p[i][j]) { dsu.unionSets(i, j); } } } unordered_map<int, vector<int>> groups; for (int i = 0; i < n; ++i) { int repr = dsu.find(i); groups[repr].push_back(i); } vector<vector<int>> answer(n, vector<int>(n,0)); for (auto& [repr, grp] : groups) { const int m = grp.size(); for (int i = 0; i < m; ++i) { int s = grp[i]; int e = grp[(i+1)%m]; answer[s][e] = 1; answer[e][s] = 1; } } build(answer); return 1; } #ifdef LOCAL int32_t main(int argc, char** argv) { assert (argc == 3); freopen(argv[1], "r", stdin); freopen(argv[2], "w", stdout); vector<vector<int>> p; int n; cin >> n; p.resize(n); for (auto& e : p) { vector<int> row(n); for (auto& el : row) cin >> el; e = row; } construct(p); return 0; } #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...