oj.uz

Submission #527271

# Submission time Handle Problem Language Result Execution time Memory
527271 2022-02-17T04:54:32 Z hmm789 Pipes (CEOI15_pipes) C++14
0 / 100
 1103 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);
	for(int i : adj[x]) {
		if(i == par) continue;
		if(root(i) == root(x)) continue;
		bool tp2 = dfs(i, x);
		if(!tp2 && tmp[tmp.size()-1] != x) {
			v[x] = 0;
			return false;
		}
	}
	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 2 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
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 187 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 353 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 584 ms 40004 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 920 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 1103 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 582 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 418 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -