Submission #527679

#	Time	Username	Problem	Language	Result	Execution time	Memory
527679		hmm789	Pipes (CEOI15_pipes)	C++14	100 / 100	1030 ms	15776 KiB

pipes

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

int p1[100000], p2[100000], sz1[100000], sz2[100000];
vector<int> adj[100000];
bool v[100000];
int dep[100000], low[100000];

int root1(int x) {
	if(p1[x] == x) return x;
	else return p1[x] = root1(p1[x]);
}
void merge1(int a, int b) {
	int x = root1(a), y = root1(b);
	if(x == y) return;
	if(sz1[x] < sz1[y]) swap(x, y);
	p1[y] = x;
	sz1[x] += sz1[y];
}
int root2(int x) {
	if(p2[x] == x) return x;
	else return p2[x] = root2(p2[x]);
}
void merge2(int a, int b) {
	int x = root2(a), y = root2(b);
	if(x == y) return;
	if(sz2[x] < sz2[y]) swap(x, y);
	p2[y] = x;
	sz2[x] += sz2[y];
}

void dfs(int x, int d, int par) {
	v[x] = 1;
	low[x] = dep[x] = d;
	bool f = true;
	for(int i : adj[x]) {
		if(i == par && f) {
			f = false;
			continue;
		} else if(v[i]) {
			low[x] = min(low[x], dep[i]);
		} else {
			dfs(i, d+1, x);
			low[x] = min(low[x], low[i]);
			if(low[i] > dep[x]) {
				cout << i+1 << " " << x+1 << '\n';
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, e, a, b;
	cin >> n >> e;
	for(int i = 0; i < n; i++) {
		p1[i] = p2[i] = i, sz1[i] = sz2[i] = 1;
	}
	for(int i = 0; i < e; i++) {
		cin >> a >> b;
		a--; b--;
		if(root1(a) != root1(b)) {
			merge1(a, b);
			adj[a].push_back(b);
			adj[b].push_back(a);
		} else if(root2(a) != root2(b)) {
			merge2(a, b);
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
	}
	for(int i = 0; i < n; i++) {
		if(!v[i]) dfs(i, 0, -1);
	}
}

• 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