Submission #1081698

#TimeUsernameProblemLanguageResultExecution timeMemory
1081698EliasPipes (CEOI15_pipes)C++17
0 / 100
661 ms13884 KiB
#include <bits/stdc++.h> using namespace std; int parent[100000]; int depth[100000]; int root[100000]; int union_parent[100000]; vector<vector<int>> children; int find(int a) { if (union_parent[a] == a) return a; return union_parent[a] = find(union_parent[a]); } bool unite(int a, int b) { a = find(a); b = find(b); if (a == b) return false; if (depth[b] > depth[a]) swap(a, b); union_parent[a] = b; return true; } vector<vector<int>> adj; int iter = 0; int dfs_reconstruct(int i, int d, int p, int r) { root[i] = r; parent[i] = p; depth[i] = d; iter++; int subtree = 1; // assert(iter < 10000); for (int c : adj[i]) { if (c == p) continue; subtree += dfs_reconstruct(c, d + 1, i, r); } return subtree; } signed main() { cin.tie(0); ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; children.resize(n); adj.resize(n); for (int i = 0; i < n; i++) { parent[i] = root[i] = union_parent[i] = i; children[i] = vector<int>{i}; depth[i] = 1; } while (m--) { int a, b; cin >> a >> b; a--, b--; // for (int i = 0; i < n; i++) // assert(root[i] == root[parent[i]] && root[i] == root[find(i)] && root[i] == root[parent[find(i)]]); if (root[a] == root[b]) { // a = find(a); // b = find(b); // while (a != b) // { // // assert(root[a] == root[b]); // if (depth[a] < depth[b]) // swap(a, b); // // assert(parent[a] != a); // unite(a, parent[a]); // a = find(a); // b = find(b); // } } else { if (children[root[a]].size() < children[root[b]].size()) swap(a, b); vector<pair<int, int>> inserts; vector<int> new_nodes; int roots = 0; for (int i : children[root[b]]) { int p = parent[i]; new_nodes.push_back(i); if (i == p) { roots++; continue; } inserts.push_back({i, p}); } assert(roots == 1); children[root[b]].clear(); for (auto [a, b] : inserts) { adj[a].push_back(b); adj[b].push_back(a); } iter = 0; assert(dfs_reconstruct(b, depth[a] + 1, a, root[a]) == new_nodes.size()); for (int node : new_nodes) { // assert(root[node] == root[a]); children[root[a]].push_back(node); // if (depth[node] < depth[find(node)]) // union_parent[find(node)] = node; } for (auto [a, b] : inserts) { adj[a].clear(); adj[b].clear(); } } } for (int i = 0; i < n; i++) { if (find(i) != find(parent[i])) cout << i + 1 << " " << parent[i] + 1 << "\n"; } }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from pipes.cpp:1:
pipes.cpp: In function 'int main()':
pipes.cpp:142:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |    assert(dfs_reconstruct(b, depth[a] + 1, a, root[a]) == new_nodes.size());
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...