oj.uz

Submission #527296

# Submission time Handle Problem Language Result Execution time Memory
527296 2022-02-17T05:34:21 Z hmm789 Pipes (CEOI15_pipes) C++14
10 / 100
 853 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100000];
int p[100000], sz[100000];
bool v[100000], v1[100000];
vector<int> tmp, tmp2;

int root(int x) {
	if(p[x] == x) return x;
	else return p[x] = root(p[x]);
}

void merge(int a, int b) {
	int x = root(a), y = root(b);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x, y);
	p[y] = x;
	sz[x] += sz[y];
}

bool dfs(int x, int par) {
	v1[x] = 1;
	tmp2.push_back(x);
	//~ cout << x+1 << endl;
	//~ for(int i : tmp) cout << i+1 << " ";
	//~ cout << endl;
	if(v[x]) {
		//~ cout << x+1 << " a" << endl;
		while(tmp[tmp.size()-1] != x) {
			merge(tmp[tmp.size()-1], x);
			tmp.erase(--tmp.end());
		}
		return false;
	}
	v[x] = 1;
	tmp.push_back(x);
	bool f = false;
	int cnt = 0;
	for(int i : adj[x]) {
		if(i == par && cnt == 0) {
			cnt++;
			continue;
		}
		if(root(i) == root(x)) continue;
		bool tp2 = dfs(i, x);
		f = true;
		if(!tp2 && tmp[tmp.size()-1] != x) {
			v[x] = 0;
			return false;
		}
	}
	if(!f) tmp.erase(--tmp.end());
	v[x] = 0;
	return true;
}
		

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, e, a, b;
	cin >> n >> e;
	pair<int, int> edg[e];
	for(int i = 0; i < e; i++) {
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		edg[i] = make_pair(a, b);
	}
	for(int i = 0; i < n; i++) p[i] = i, sz[i] = 1;
	for(int i = 0; i < n; i++) {
		if(!v1[i]) {
			for(int i : tmp2) v[i] = 0;
			tmp2.clear();
			dfs(i, -1);
		}
		tmp.clear();
	}
	for(int i = 0; i < e; i++) {
		if(root(edg[i].first) != root(edg[i].second)) cout << edg[i].first+1 << " " << edg[i].second+1 << '\n';
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 15260 KB Output is correct
2 Correct 100 ms 14740 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 809 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 853 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 560 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 378 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -