oj.uz

Submission #527679

# Submission time Handle Problem Language Result Execution time Memory
527679 2022-02-18T02:08:25 Z hmm789 Pipes (CEOI15_pipes) C++14
100 / 100
 1030 ms 15776 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3292 KB Output is correct
2 Correct 5 ms 3028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 3136 KB Output is correct
2 Correct 87 ms 2880 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 3856 KB Output is correct
2 Correct 174 ms 3332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 5796 KB Output is correct
2 Correct 209 ms 5412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 11832 KB Output is correct
2 Correct 339 ms 7792 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 13196 KB Output is correct
2 Correct 474 ms 9944 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 15772 KB Output is correct
2 Correct 661 ms 10044 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 15776 KB Output is correct
2 Correct 885 ms 10032 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 15108 KB Output is correct
2 Correct 916 ms 12004 KB Output is correct