Submission #1342563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1342563		goats_9	Pipes (CEOI15_pipes)	C++20	0 / 100	593 ms	3012 KiB

pipes

/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class DSU {
	int n;
	vector<int> p, rank;
	vector<pair<int, int>> bridge;

public:
	DSU (int _n) : n(_n), p(n), rank(n), bridge(n, {-1, -1}) { iota(p.begin(), p.end(), 0); }
	int get(int i) { return (p[i] == i) ? p[i] : (p[i] = get(p[i])); }
	void unite(int i, int j) {
		i = get(i), j = get(j);
		if (i == j) {
			bridge[i] = {-1, -1};
			return;
		}
		if (rank[i] < rank[j]) swap(i, j);
		if (rank[i] == rank[j]) ++rank[i];
		p[j] = i;
		bridge[j] = {i, j};
	}
	void bridges() {
		for (auto [u, v] : bridge) {
			if (u == -1) continue;
			cout << u + 1 << ' ' << v + 1 << '\n';
		}
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;
	DSU dsu(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		dsu.unite(--u, --v);
	}
	dsu.bridges();
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10