oj.uz

Submission #380616

# Submission time Handle Problem Language Result Execution time Memory
380616 2021-03-22T13:10:20 Z KoD Simurgh (IOI17_simurgh) C++17
51 / 100
 3000 ms 20240 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()));
	int counter = 0;
	const auto exchange = [&](const int e, const int f) {
		tree.erase(e);
		tree.insert(f);
		counter += 1;
		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;
		}
	}
	assert(counter <= 2 * n);
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 496 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 496 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 4 ms 492 KB correct
17 Correct 4 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 512 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 492 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 512 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 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 2 ms 364 KB correct
33 Correct 2 ms 364 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 496 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 4 ms 492 KB correct
17 Correct 4 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 512 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 492 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 512 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 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 2 ms 364 KB correct
33 Correct 2 ms 364 KB correct
34 Correct 361 ms 4980 KB correct
35 Correct 330 ms 4844 KB correct
36 Correct 226 ms 3624 KB correct
37 Correct 20 ms 620 KB correct
38 Correct 332 ms 4972 KB correct
39 Correct 288 ms 4332 KB correct
40 Correct 223 ms 3624 KB correct
41 Correct 355 ms 4972 KB correct
42 Correct 334 ms 5100 KB correct
43 Correct 98 ms 2924 KB correct
44 Correct 67 ms 2284 KB correct
45 Correct 83 ms 2668 KB correct
46 Correct 54 ms 2028 KB correct
47 Correct 20 ms 1132 KB correct
48 Correct 6 ms 364 KB correct
49 Correct 9 ms 620 KB correct
50 Correct 19 ms 1132 KB correct
51 Correct 85 ms 2740 KB correct
52 Correct 65 ms 2284 KB correct
53 Correct 54 ms 2156 KB correct
54 Correct 96 ms 3052 KB correct
55 Correct 140 ms 2796 KB correct
56 Correct 141 ms 2668 KB correct
57 Correct 168 ms 2668 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 2099 ms 13340 KB correct
4 Execution timed out 3074 ms 20240 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 364 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 496 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 364 KB correct
14 Correct 4 ms 492 KB correct
15 Correct 4 ms 492 KB correct
16 Correct 4 ms 492 KB correct
17 Correct 4 ms 492 KB correct
18 Correct 2 ms 364 KB correct
19 Correct 4 ms 512 KB correct
20 Correct 4 ms 492 KB correct
21 Correct 4 ms 492 KB correct
22 Correct 2 ms 492 KB correct
23 Correct 2 ms 364 KB correct
24 Correct 2 ms 364 KB correct
25 Correct 1 ms 364 KB correct
26 Correct 2 ms 512 KB correct
27 Correct 2 ms 364 KB correct
28 Correct 1 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 2 ms 364 KB correct
33 Correct 2 ms 364 KB correct
34 Correct 361 ms 4980 KB correct
35 Correct 330 ms 4844 KB correct
36 Correct 226 ms 3624 KB correct
37 Correct 20 ms 620 KB correct
38 Correct 332 ms 4972 KB correct
39 Correct 288 ms 4332 KB correct
40 Correct 223 ms 3624 KB correct
41 Correct 355 ms 4972 KB correct
42 Correct 334 ms 5100 KB correct
43 Correct 98 ms 2924 KB correct
44 Correct 67 ms 2284 KB correct
45 Correct 83 ms 2668 KB correct
46 Correct 54 ms 2028 KB correct
47 Correct 20 ms 1132 KB correct
48 Correct 6 ms 364 KB correct
49 Correct 9 ms 620 KB correct
50 Correct 19 ms 1132 KB correct
51 Correct 85 ms 2740 KB correct
52 Correct 65 ms 2284 KB correct
53 Correct 54 ms 2156 KB correct
54 Correct 96 ms 3052 KB correct
55 Correct 140 ms 2796 KB correct
56 Correct 141 ms 2668 KB correct
57 Correct 168 ms 2668 KB correct
58 Correct 1 ms 364 KB correct
59 Correct 1 ms 364 KB correct
60 Correct 2099 ms 13340 KB correct
61 Execution timed out 3074 ms 20240 KB Time limit exceeded
62 Halted 0 ms 0 KB -