oj.uz

Submission #527678

# Submission time Handle Problem Language Result Execution time Memory
527678 2022-02-18T02:04:30 Z hmm789 Pipes (CEOI15_pipes) C++14
100 / 100
 943 ms 16160 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], par[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) {
	v[x] = 1;
	low[x] = dep[x] = d;
	bool f = true;
	for(int i : adj[x]) {
		if(i == par[x] && f) {
			f = false;
			continue;
		} else if(v[i]) {
			low[x] = min(low[x], dep[i]);
		} else {
			par[i] = x;
			dfs(i, d+1);
			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]) {
			par[i] = -1;
			dfs(i, 0);
		}
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 3284 KB Output is correct
2 Correct 6 ms 3028 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 3984 KB Output is correct
2 Correct 185 ms 3328 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 5796 KB Output is correct
2 Correct 200 ms 5584 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 12172 KB Output is correct
2 Correct 267 ms 8140 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 13580 KB Output is correct
2 Correct 454 ms 10416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 16160 KB Output is correct
2 Correct 594 ms 10432 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 16156 KB Output is correct
2 Correct 758 ms 10520 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 15388 KB Output is correct
2 Correct 896 ms 12308 KB Output is correct