oj.uz

Submission #527674

# Submission time Handle Problem Language Result Execution time Memory
527674 2022-02-18T01:58:33 Z hmm789 Pipes (CEOI15_pipes) C++17
0 / 100
 978 ms 26144 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;
	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]) dfs(i, -1);
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2680 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3404 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 8616 KB Output is correct
2 Incorrect 82 ms 8264 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 13560 KB Output is correct
2 Incorrect 165 ms 14660 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 251 ms 22084 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 14072 KB Output is correct
2 Incorrect 276 ms 9532 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 15852 KB Output is correct
2 Incorrect 565 ms 12160 KB Wrong number of edges
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 645 ms 20156 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 774 ms 26144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 978 ms 20984 KB Memory limit exceeded
2 Halted 0 ms 0 KB -