oj.uz

답안 #244523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244523 2020-07-04T09:01:36 Z shenxy Pipes (CEOI15_pipes) C++11
40 / 100
 1744 ms 16668 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;
			p2 = p1;
			p1 = ii(i, 0);
			if (p2.first != -1) parent[p1.first] = p2;
			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]) {
					lca = p;
					break;
				} else visited[p] = true;
				if (visited[q]) {
					lca = q;
					break;
				} else visited[q] = true;
				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] = false;
				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] = false;
				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] = 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(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:103: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:106: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 Correct 4 ms 256 KB Output is correct
2 Incorrect 5 ms 432 KB Wrong number of edges

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 640 KB Output is correct
2 Incorrect 9 ms 640 KB Wrong number of edges

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 547 ms 4844 KB Output is correct
2 Incorrect 514 ms 4688 KB Wrong number of edges

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 884 ms 5348 KB Output is correct
2 Correct 853 ms 4960 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1165 ms 6504 KB Output is correct
2 Incorrect 1090 ms 6504 KB Wrong number of edges

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1429 ms 6540 KB Output is correct
2 Incorrect 1389 ms 6888 KB Wrong number of edges

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1744 ms 6376 KB Output is correct
2 Runtime error 1701 ms 16668 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)