Submission #527275

#	Time	Username	Problem	Language	Result	Execution time	Memory
527275		hmm789	Pipes (CEOI15_pipes)	C++14	0 / 100	902 ms	65540 KiB

pipes

#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;
	for(int i : adj[x]) {
		if(i == par) 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10