oj.uz

답안 #244517

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244517 2020-07-04T08:45:54 Z shenxy Pipes (CEOI15_pipes) C++11
0 / 100
 5000 ms 6120 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<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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 640 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 576 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 294 ms 1016 KB Wrong number of edges
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5052 ms 1792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5082 ms 4328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5072 ms 4972 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5075 ms 6116 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5064 ms 6120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5057 ms 5868 KB Time limit exceeded
2 Halted 0 ms 0 KB -