Submission #1228709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228709		kaiboy	Pipes (CEOI15_pipes)	C++20	100 / 100	545 ms	13996 KiB

pipes

// coached by rainboy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100000;

int ds0[N], ds1[N], ta[N], tb[N];
vector<int> ej[N];

int find(int *ds, int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}

bool join(int *ds, int i, int j) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return false;
	if (ds[i] == ds[j])
		ds[i]--;
	if (ds[i] < ds[j])
		swap(i, j);
	ds[i] = j;
	return true;
}

void dfs(int p, int i) {
	static int t = 1;
	ta[i] = tb[i] = t++;
	int p_ = p;
	for (int j : ej[i])
		if (j == p_)
			p_ = -1;
		else if (ta[j])
			tb[i] = min(tb[i], ta[j]);
		else {
			dfs(i, j);
			tb[i] = min(tb[i], tb[j]);
		}
	if (p != -1 && ta[i] == tb[i])
		cout << p + 1 << ' ' << i + 1 << '\n';
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		ds0[i] = ds1[i] = -1;
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		if (join(ds0, i, j) || join(ds1, i, j)) {
			ej[i].push_back(j);
			ej[j].push_back(i);
		}
	}
	for (int i = 0; i < n; i++)
		if (!ta[i])
			dfs(-1, i);
	return 0;
}

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