제출 #1228668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228668		kaiboy	Pipes (CEOI15_pipes)	C++20	0 / 100	5095 ms	8256 KiB

pipes

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 100000;

int ii[N], jj[N]; bool bridge[N];
int ds[N], ds_[N], hh[N], dd[N];
vector<int> *eh[N]; bool visited[N];

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

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] == ds[j])
		ds[i]--;
	if (ds[i] < ds[j])
		swap(i, j);
	ds[i] = j;
	if (hh[j] != -1 && !bridge[hh[j]])
		hh[j] = hh[i];
	dd[j] = min(dd[j], dd[i]);
	for (int &h : *eh[i])
		eh[j]->push_back(h);
	delete eh[i];
}

int find_(int i) {
	return ds_[i] < 0 ? i : (ds_[i] = find_(ds_[i]));
}

void dfs(int h_, int i, int d) {
	hh[i] = h_, dd[i] = d++;
	for (int &h : *eh[i]) {
		int j = i ^ find(ii[h]) ^ find(jj[h]);
		if (j == i) {
			swap(h, *eh[i]->rbegin());
			eh[i]->pop_back();
			continue;
		}
		if (h != h_)
			dfs(h, j, d);
	}
}

bool join_(int i, int j, int h) {
	int i_ = i; i = find_(i);
	int j_ = j; j = find_(j);
	if (i == j)
		return false;
	if (ds_[i] == ds_[j])
		ds_[i]--;
	if (ds_[i] < ds_[j])
		swap(i, j);
	ds_[i] = j;
	i = i_, j = j_;
	bridge[h] = true;
	eh[i]->push_back(h);
	eh[j]->push_back(h);
	dfs(h, i, dd[j] + 1);
	return true;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	int m_ = 0;
	for (int i = 0; i < n; i++)
		ds[i] = ds_[i] = hh[i] = -1, eh[i] = new vector<int>;
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		ii[m_] = i, i = find(i);
		jj[m_] = j, j = find(j);
		if (join_(i, j, m_)) {
			m_++;
			continue;
		}
		while (i != j) {
			if (dd[i] < dd[j])
				swap(i, j);
			int h = hh[i]; bridge[h] = false;
			int p = i ^ find(ii[h]) ^ find(jj[h]);
			join(i, p), i = find(i), j = find(j);
		}
	}
	for (int h = 0; h < m_; h++)
		if (bridge[h])
			cout << ii[h] + 1 << ' ' << jj[h] + 1 << '\n';
	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