Submission #244531

#	Time	Username	Problem	Language	Result	Execution time	Memory
244531		shenxy	Pipes (CEOI15_pipes)	C++11	100 / 100	1805 ms	6624 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<int, ii> bridges;
	UFDS* cc;
	UFDSpp* bridgecc;
	vector<ii> 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(ii(-1, -1));
		for (int i = 0; i < N; ++i) visited.push_back(0);
	}
	void add_edge(int id, 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);
			ii p1 = ii(-1, -1), p2 = ii(-1, -1);
			int i;
			for (i = bridgecc -> get_root(a); parent[i].first != -1; i = bridgecc -> get_root(parent[i].first)) {
				if (p2.first != -1) parent[p1.first] = p2;
				p2 = p1;
				p1 = ii(i, parent[i].second);
			}
			if (p2.first != -1) parent[p1.first] = p2;
			if (p1.first != -1) parent[i] = p1;
			parent[bridgecc -> get_root(a)] = ii(bridgecc -> get_root(b), id);
			cc -> merge(a, b);
			bridges[id] = 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] == 2) {
					lca = p;
					break;
				} else visited[p] = 1;
				if (visited[q] == 1) {
					lca = q;
					break;
				} else visited[q] = 2;
				if (parent[p].first != -1) p = bridgecc -> get_root(parent[p].first);
				if (parent[q].first != -1) q = bridgecc -> get_root(parent[q].first);
			}
			for (int i = bridgecc -> get_root(a); i != lca; i = bridgecc -> get_root(parent[i].first)) {
				visited[i] = 0;
				bridges.erase(parent[i].second);
				bridgecc -> merge(lca, i);
			}
			for (int i = bridgecc -> get_root(b); i != lca; i = bridgecc -> get_root(parent[i].first)) {
				visited[i] = 0;
				bridges.erase(parent[i].second);
				bridgecc -> merge(lca, i);
			}
			for (int i = lca; i != -1 && visited[i]; i = parent[i].first == -1 ? -1 : bridgecc -> get_root(parent[i].first)) visited[i] = 0;
		}
	}
};
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(i, 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:101: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:104: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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10