Submission #244517

#	Time	Username	Problem	Language	Result	Execution time	Memory
244517		shenxy	Pipes (CEOI15_pipes)	C++11	0 / 100	5082 ms	6120 KiB

pipes

//happy birthday errorgorn
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef pair<int, int> ii;
struct UFDS {
	vector<int> parent, rankof;
	UFDS(int N) {
		for (int i = 0; i < N; ++i) parent.push_back(i), rankof.push_back(1);
	}
	int find_parent(int i) {
		if (parent[i] == i) return i;
		return parent[i] = find_parent(parent[i]);
	}
	void merge(int p, int q) {
		p = find_parent(p), q = find_parent(q);
		if (p == q) return;
		if (rankof[p] > rankof[q]) parent[q] = p, rankof[p] += rankof[q];
		else parent[p] = q, rankof[q] += rankof[p];
	}
};
struct UFDSpp {
	vector<int> parent, rankof, root;
	UFDSpp(int N) {
		for (int i = 0; i < N; ++i) parent.push_back(i), rankof.push_back(0), root.push_back(i);
	}
	int find_parent(int i) {
		if (parent[i] == i) return i;
		return parent[i] = find_parent(parent[i]);
	}
	int get_root(int i) {
		return root[find_parent(i)];
	}
	void merge(int p, int q) {
		p = find_parent(p), q = find_parent(q);
		if (p == q) return;
		if (rankof[p] == rankof[q]) ++rankof[p];
		if (rankof[p] > rankof[q]) parent[q] = p;
		else root[q] = root[p], parent[p] = q;
	}
};
struct BridgeTree {
	map<ii, ii> bridges;
	UFDS* cc;
	UFDSpp* bridgecc;
	vector<int> parent;
	vector<char> visited;
	BridgeTree(int N) {
		cc = new UFDS(N);
		bridgecc = new UFDSpp(N);
		for (int i = 0; i < N; ++i) parent.push_back(-1);
		for (int i = 0; i < N; ++i) visited.push_back(0);
	}
	void add_edge(int a, int b) {
		if (cc -> find_parent(a) != cc -> find_parent(b)) {
			if (cc -> rankof[cc -> find_parent(a)] > cc -> rankof[cc -> find_parent(b)]) swap(a, b);
			int p1 = -1, p2 = -1, i;
			for (i = bridgecc -> get_root(a); parent[i] != -1; i = bridgecc -> get_root(parent[i])) {
				if (p2 != -1) parent[p1] = p2;
				p2 = p1;
				p1 = i;
			}
			if (p2 != -1) parent[p1] = p2;
			p2 = p1;
			p1 = i;
			if (p2 != -1) parent[p1] = p2;
			parent[bridgecc -> get_root(a)] = bridgecc -> get_root(b);
			cc -> merge(a, b);
			bridges[ii(bridgecc -> get_root(b), bridgecc -> get_root(a))] = ii(a, b);
		} else if (bridgecc -> find_parent(a) != bridgecc -> find_parent(b)) {
			int p = bridgecc -> get_root(a), q = bridgecc -> get_root(b), lca;
			while (true) {
				if (visited[p]) {
					lca = p;
					break;
				} else visited[p] = true;
				if (visited[q]) {
					lca = q;
					break;
				} else visited[q] = true;
				p = bridgecc -> get_root(parent[p]);
				q = bridgecc -> get_root(parent[q]);
			}
			for (int i = bridgecc -> get_root(a); i != lca; i = bridgecc -> get_root(parent[i])) {
				visited[i] = false;
				bridges.erase(ii(bridgecc -> get_root(parent[i]), i));
				bridges.erase(ii(i, bridgecc -> get_root(parent[i])));
				bridgecc -> merge(lca, i);
			}
			for (int i = bridgecc -> get_root(b); i != lca; i = bridgecc -> get_root(parent[i])) {
				visited[i] = false;
				bridges.erase(ii(bridgecc -> get_root(parent[i]), i));
				bridges.erase(ii(i, bridgecc -> get_root(parent[i])));
				bridgecc -> merge(lca, i);
			}
			for (int i = lca; visited[i]; i = bridgecc -> get_root(parent[i])) visited[i] = false;
		}
	}
};
int main() {
	int N, M, u, v;
	scanf("%d %d", &N, &M);
	BridgeTree bride(N);
	for (int i = 0; i < M; ++i) {
		scanf("%d %d", &u, &v);
		bride.add_edge(u - 1, v - 1);
	}
	for (auto i: bride.bridges) printf("%d %d\n", i.second.first + 1, i.second.second + 1);
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:104:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

• 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