oj.uz

답안 #244531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244531 2020-07-04T09:18:21 Z shenxy Pipes (CEOI15_pipes) C++11
100 / 100
 1805 ms 6624 KB 
//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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 10 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 512 KB Output is correct
2 Correct 147 ms 632 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 258 ms 1024 KB Output is correct
2 Correct 298 ms 1024 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 410 ms 1916 KB Output is correct
2 Correct 357 ms 2036 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 4796 KB Output is correct
2 Correct 495 ms 4572 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 868 ms 5360 KB Output is correct
2 Correct 838 ms 5016 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1216 ms 6624 KB Output is correct
2 Correct 1104 ms 6492 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1497 ms 6516 KB Output is correct
2 Correct 1368 ms 6492 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1805 ms 6260 KB Output is correct
2 Correct 1654 ms 6240 KB Output is correct