oj.uz

답안 #380615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380615 2021-03-22T13:07:58 Z KoD Simurgh (IOI17_simurgh) C++17
51 / 100
 3000 ms 21228 KB 
#include <bits/stdc++.h>
#include "simurgh.h"

template <class T>
using Vec = std::vector<T>;

template <class F>
struct RecLambda: private F {
	explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
	template <class... Args>
	decltype(auto) operator () (Args&&... args) const {
		return F::operator()(*this, std::forward<Args>(args)...);
	}
};

struct DSU {
	Vec<int> par;
	DSU(const int n): par(n, -1) { }
	int find(const int u) {
		return par[u] < 0 ? u : par[u] = find(par[u]);
	}	
	bool merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return false;
		if (par[x] > par[y]) std::swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}
};

Vec<int> find_roads(int n, Vec<int> u, Vec<int> v) {
	const int m = (int) u.size();
	Vec<Vec<int>> graph(n);
	std::map<std::pair<int, int>, int> edge;
	for (int i = 0; i < m; ++i) {
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
		edge[{ u[i], v[i] }] = i;
		edge[{ v[i], u[i] }] = i;
	}
	std::set<int> tree;
	Vec<int> back;
	Vec<int> parent(n), depth(n, -1);
	RecLambda([&](auto dfs, const int u, const int p, const int d) -> void {
		parent[u] = p;
		depth[u] = d;
		for (const auto v: graph[u]) {
			if (v != p) {
				if (depth[v] == -1) {
					tree.insert(edge[{ u, v }]);
					dfs(v, u, d + 1);
				}
				else {
					if (depth[v] < depth[u]) {
						back.push_back(edge[{ u, v }]);
					}
				}
			}
		}
	})(0, -1, 0);
	assert((int) tree.size() == n - 1);
	const auto base = count_common_roads(Vec<int>(tree.begin(), tree.end()));
	const auto exchange = [&](const int e, const int f) {
		tree.erase(e);
		tree.insert(f);
		const auto ret = count_common_roads(Vec<int>(tree.begin(), tree.end()));
		tree.erase(f);
		tree.insert(e);
		return ret;
	};
	Vec<int> state(m);
	for (const auto e: back) { 
		int a = u[e], b = v[e];
		if (depth[a] < depth[b]) {
			std::swap(a, b);
		}
		Vec<int> done, same, differ;
		while (a != b) {
			const auto p = parent[a];
			const auto f = edge[{ a, p }];
			if (state[f] == 0) {
				const auto tmp = exchange(f, e);
				if (tmp == base) {
					same.push_back(f);
				}
				else {
					state[e] = (tmp > base ? 1 : -1);
					differ.push_back(f);
				}
			}
			else {
				done.push_back(f);
			}
			a = p;
		}
		if (state[e] == 0 && same.size() + differ.size() > 0) {
			if (done.empty()) {
				state[e] = -1;
			}
			else {
				const auto f = done.front();
				const auto tmp = exchange(f, e);
				if (tmp == base) {
					state[e] = state[f];
				}
				else {
					state[e] = -state[f];
				}
			}
		}
		for (const auto f: same) {
			state[f] = state[e];
		}
		for (const auto f: differ) {
			state[f] = -state[e];
		}
	}
	for (const auto e: tree) {
		if (state[e] == 0) {
			state[e] = 1;
		}
	}
	const auto count = [&](const Vec<int> &es) {
		Vec<int> ask;
		ask.reserve(n - 1);
		DSU dsu(n);
		for (const auto e: es) {
			ask.push_back(e);
			dsu.merge(u[e], v[e]);
		}
		int sum = 0;
		for (const auto e: tree) {
			if (dsu.merge(u[e], v[e])) {
				ask.push_back(e);
				sum += (state[e] == 1);
			}
		}
		return count_common_roads(ask) - sum;
	};
	for (int i = 0; i < n; ++i) {
		std::set<int> remain;
		for (const auto j: graph[i]) {
			const auto e = edge[{ i, j }];
			if (state[e] == 0) {
				remain.insert(e);
			}
		}
		while (true) {
			Vec<int> vec(remain.begin(), remain.end());
			if (count(vec) == 0) {
				break;
			}
			while (vec.size() > 1) {
				const auto m = (int) vec.size() / 2;
				Vec<int> left(vec.begin(), vec.begin() + m);
				Vec<int> right(vec.begin() + m, vec.end());
				if (count(left) > 0) {
					vec = std::move(left);
				}
				else {
					vec = std::move(right);
				}
			}
			state[vec[0]] = 1;
			remain.erase(vec[0]);
		}
		for (const auto e: remain) {
			state[e] = -1;
		}
	}
	Vec<int> ret;
	for (int i = 0; i < m; ++i) {
		if (state[i] == 1) {
			ret.push_back(i);
		}
	}
	return ret;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 5 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 6 ms 620 KB correct
17 Correct 6 ms 640 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 492 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 512 KB correct
23 Correct 3 ms 364 KB correct
24 Correct 3 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 2 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 364 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 2 ms 364 KB correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 5 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 6 ms 620 KB correct
17 Correct 6 ms 640 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 492 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 512 KB correct
23 Correct 3 ms 364 KB correct
24 Correct 3 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 2 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 364 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 2 ms 364 KB correct
34 Correct 350 ms 5228 KB correct
35 Correct 331 ms 5036 KB correct
36 Correct 224 ms 3752 KB correct
37 Correct 20 ms 620 KB correct
38 Correct 339 ms 5228 KB correct
39 Correct 293 ms 4460 KB correct
40 Correct 258 ms 3752 KB correct
41 Correct 351 ms 5228 KB correct
42 Correct 346 ms 5168 KB correct
43 Correct 108 ms 3180 KB correct
44 Correct 69 ms 2412 KB correct
45 Correct 84 ms 2796 KB correct
46 Correct 55 ms 2156 KB correct
47 Correct 21 ms 1132 KB correct
48 Correct 6 ms 364 KB correct
49 Correct 10 ms 620 KB correct
50 Correct 20 ms 1132 KB correct
51 Correct 85 ms 2796 KB correct
52 Correct 65 ms 2412 KB correct
53 Correct 53 ms 2156 KB correct
54 Correct 115 ms 3052 KB correct
55 Correct 145 ms 2796 KB correct
56 Correct 145 ms 2796 KB correct
57 Correct 145 ms 2924 KB correct

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 2107 ms 13840 KB correct
4 Execution timed out 3052 ms 21228 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 384 KB correct
3 Correct 1 ms 512 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 256 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 384 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 5 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 6 ms 620 KB correct
17 Correct 6 ms 640 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 492 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 512 KB correct
23 Correct 3 ms 364 KB correct
24 Correct 3 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 364 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 2 ms 364 KB correct
29 Correct 1 ms 364 KB correct
30 Correct 2 ms 364 KB correct
31 Correct 2 ms 364 KB correct
32 Correct 3 ms 512 KB correct
33 Correct 2 ms 364 KB correct
34 Correct 350 ms 5228 KB correct
35 Correct 331 ms 5036 KB correct
36 Correct 224 ms 3752 KB correct
37 Correct 20 ms 620 KB correct
38 Correct 339 ms 5228 KB correct
39 Correct 293 ms 4460 KB correct
40 Correct 258 ms 3752 KB correct
41 Correct 351 ms 5228 KB correct
42 Correct 346 ms 5168 KB correct
43 Correct 108 ms 3180 KB correct
44 Correct 69 ms 2412 KB correct
45 Correct 84 ms 2796 KB correct
46 Correct 55 ms 2156 KB correct
47 Correct 21 ms 1132 KB correct
48 Correct 6 ms 364 KB correct
49 Correct 10 ms 620 KB correct
50 Correct 20 ms 1132 KB correct
51 Correct 85 ms 2796 KB correct
52 Correct 65 ms 2412 KB correct
53 Correct 53 ms 2156 KB correct
54 Correct 115 ms 3052 KB correct
55 Correct 145 ms 2796 KB correct
56 Correct 145 ms 2796 KB correct
57 Correct 145 ms 2924 KB correct
58 Correct 1 ms 364 KB correct
59 Correct 1 ms 364 KB correct
60 Correct 2107 ms 13840 KB correct
61 Execution timed out 3052 ms 21228 KB Time limit exceeded
62 Halted 0 ms 0 KB -