Submission #1245293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245293		pasta	Pipes (CEOI15_pipes)	C++20	100 / 100	582 ms	14504 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define pb	push_back
// #define int	ll
 
const int maxn = 1e5 + 10;
 
int par1[maxn], par2[maxn], sz1[maxn], sz2[maxn];
 
int get1(int v) {
	if (par1[v] == v)
		return v;
	else
		return par1[v] = get1(par1[v]);
}
 
bool merge1(int v, int u) {
	v = get1(v);
	u = get1(u);
	if (v == u)
		return false;
	if (sz1[v] < sz1[u])
		swap(v, u);
	sz1[v] += sz1[u];
	par1[u] = v;
	return true;
}
 
int get2(int v) {
	if (par2[v] == v)
		return v;
	else
		return par2[v] = get2(par2[v]);
}
 
bool merge2(int v, int u) {
	v = get2(v);
	u = get2(u);
	if (v == u)
		return false;
	if (sz2[v] < sz2[u])
		swap(v, u);
	sz2[v] += sz2[u];
	par2[u] = v;
	return true;
}
 
int n, m, dep[maxn];
vector<int> G[maxn];
bool mark[maxn];
vector<pii> candi;
 
int dfs(int v, int p, int depth) {
	mark[v] = 1;
	dep[v] = depth;
	int res = depth, cnt = 0;
	for (int u : G[v]) {
		if (u == p && cnt == 0) {
			cnt++;
			continue;
		}
		if (mark[u])
			res = min(res, dep[u]);
		else
			res = min(res, dfs(u, v, depth + 1));
	}
	if (p != 0 && res == depth) {
		candi.pb({p, v});
	}
	return res;
}
 
void cutEdge() {
	for (int i = 1; i <= n; i++) {
		if (!mark[i])
			dfs(i, 0, 0);
	}
	for (auto [v, u] : candi)
		cout << v << ' ' << u << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		sz1[i] = sz2[i] = 1;
		par1[i] = par2[i] = i;
	}
 
	for (int i = 1; i <= m; i++) {
		int v, u;
		cin >> v >> u;
		
		if (get1(v) != get1(u)) {
			merge1(v, u);
			G[v].pb(u);
			G[u].pb(v);
			continue;
		}
		else if (get2(v) != get2(u)) {
			merge2(v, u);
			G[v].pb(u);
			G[u].pb(v);
			continue;
		}
	}
	// cout << "kir" << '\n';
	cutEdge();
}

• 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