oj.uz

Submission #432669

# Submission time Handle Problem Language Result Execution time Memory
432669 2021-06-18T12:16:28 Z KoD Simurgh (IOI17_simurgh) C++17
100 / 100
 420 ms 5996 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)...);
	}
};

Vec<int> find_roads(int n, Vec<int> a, Vec<int> b) {
	const int m = (int) a.size();
	Vec<Vec<std::pair<int, int>>> graph(n);
	for (int i = 0; i < m; ++i) {
		graph[a[i]].emplace_back(b[i], i);
		graph[b[i]].emplace_back(a[i], i);
	}
	Vec<int> depth(n, -1), pedge(n, -1);
	depth[0] = 0;
	RecLambda([&](auto&& dfs, const int u) -> void {
		for (const auto [v, e] : graph[u]) {
			if (e == pedge[u]) continue;
			if (depth[v] == -1) {
				depth[v] = depth[u] + 1;
				pedge[v] = e;
				dfs(v);
			}
		}
	})(0);
	for (int i = 0; i < m; ++i) {
		if (depth[a[i]] > depth[b[i]]) {
			std::swap(a[i], b[i]);
		}
	}
	Vec<int> type(m);
	std::set<int> tree;
	for (int u = 1; u < n; ++u) {
		tree.insert(pedge[u]);
	}
	const int tree_cnt = count_common_roads(Vec<int>(tree.begin(), tree.end()));
	for (int e = 0; e < m; ++e) {
		if (tree.find(e) != tree.end()) continue;
		Vec<int> done, same, dif;
		for (int u = b[e]; u != a[e];) {
			const int f = pedge[u];
			if (type[f] == 0) {
				tree.erase(f);
				tree.insert(e);
				const int tmp = count_common_roads(Vec<int>(tree.begin(), tree.end()));
				tree.erase(e);
				tree.insert(f);
				if (tmp != tree_cnt) {
					type[e] = (tmp > tree_cnt ? 1 : -1);
					dif.push_back(f);
				} else {
					same.push_back(f);
				}
				(tmp == tree_cnt ? same : dif).push_back(f);
			} else {
				done.push_back(f);
			}
			u = a[f];
		}
		if (same.empty() and dif.empty()) continue;
		if (type[e] == 0) {
			if (done.empty()) {
				type[e] = -1;
			} else {
				const int f = done[0];
				tree.erase(f);
				tree.insert(e);
				const int tmp = count_common_roads(Vec<int>(tree.begin(), tree.end()));
				tree.erase(e);
				tree.insert(f);
				type[e] = type[f] * (tmp == tree_cnt ? 1 : -1);
			}
		}
		for (const int f : same) {
			type[f] = type[e];
		}
		for (const int f : dif) {
			type[f] = type[e] * -1;
		}
	}
	for (const int e : tree) {
		if (type[e] == 0) {
			type[e] = 1;
		}
	}
	const auto count = [&](const Vec<int>& vec) {
		if (vec.empty()) {
			return 0;
		}
		Vec<char> used(n);
		for (const int e : vec) {
			used[b[e]] = true;
		}
		Vec<int> ask = vec;
		int cnt = 0;
		for (int u = 1; u < n; ++u) {
			if (!used[u]) {
				ask.push_back(pedge[u]);
				cnt += (type[pedge[u]] == 1);
			}
		}
		const int ret = count_common_roads(ask) - cnt;
		for (const int e : vec) {
			used[b[e]] = false;
		}
		return ret;
	};
	for (int u = 0; u < n; ++u) {
		std::set<int> remain;
		for (const auto [v, e] : graph[u]) {
			if (b[e] == v and type[e] == 0) {
				remain.insert(e);
			}
		}
		const int all = count(Vec<int>(remain.begin(), remain.end()));
		for (int step = 0; step < all; ++step) {
			Vec<int> cand(remain.begin(), remain.end());
			while (cand.size() > 1) {
				const int mid = (int) cand.size() / 2;
				Vec<int> left(cand.begin(), cand.begin() + mid);
				Vec<int> right(cand.begin() + mid, cand.end());
				if (count(left) > 0) {
					cand = std::move(left);
				} else {
					cand = std::move(right);
				}
			}
			const int e = cand[0];
			type[e] = 1;
			remain.erase(e);	
		}
		for (const int e : remain) {
			type[e] = -1;
		}
	}
	Vec<int> ret;
	for (int i = 0; i < m; ++i) {
		if (type[i] == 1) {
			ret.push_back(i);
		}
	}
	return ret;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 288 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 288 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 2 ms 300 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 204 KB correct
24 Correct 1 ms 204 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 204 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 288 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 204 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 288 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 288 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 2 ms 300 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 204 KB correct
24 Correct 1 ms 204 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 204 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 288 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 204 KB correct
34 Correct 60 ms 1644 KB correct
35 Correct 63 ms 1612 KB correct
36 Correct 52 ms 1356 KB correct
37 Correct 8 ms 332 KB correct
38 Correct 59 ms 1632 KB correct
39 Correct 52 ms 1516 KB correct
40 Correct 43 ms 1356 KB correct
41 Correct 57 ms 1632 KB correct
42 Correct 57 ms 1620 KB correct
43 Correct 25 ms 1184 KB correct
44 Correct 20 ms 844 KB correct
45 Correct 22 ms 968 KB correct
46 Correct 18 ms 848 KB correct
47 Correct 10 ms 484 KB correct
48 Correct 3 ms 332 KB correct
49 Correct 5 ms 296 KB correct
50 Correct 10 ms 556 KB correct
51 Correct 28 ms 972 KB correct
52 Correct 20 ms 888 KB correct
53 Correct 18 ms 848 KB correct
54 Correct 30 ms 1100 KB correct
55 Correct 30 ms 972 KB correct
56 Correct 27 ms 972 KB correct
57 Correct 28 ms 972 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 218 ms 4268 KB correct
4 Correct 381 ms 5988 KB correct
5 Correct 420 ms 5956 KB correct
6 Correct 373 ms 5976 KB correct
7 Correct 368 ms 5988 KB correct
8 Correct 378 ms 5996 KB correct
9 Correct 386 ms 5964 KB correct
10 Correct 391 ms 5992 KB correct
11 Correct 377 ms 5944 KB correct
12 Correct 414 ms 5964 KB correct
13 Correct 0 ms 296 KB correct
14 Correct 398 ms 5952 KB correct
15 Correct 402 ms 5956 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 0 ms 204 KB correct
5 Correct 1 ms 288 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 204 KB correct
10 Correct 1 ms 288 KB correct
11 Correct 1 ms 204 KB correct
12 Correct 1 ms 204 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 2 ms 300 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 2 ms 332 KB correct
18 Correct 1 ms 204 KB correct
19 Correct 2 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 2 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 204 KB correct
24 Correct 1 ms 204 KB correct
25 Correct 1 ms 204 KB correct
26 Correct 1 ms 204 KB correct
27 Correct 1 ms 332 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 288 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 332 KB correct
33 Correct 1 ms 204 KB correct
34 Correct 60 ms 1644 KB correct
35 Correct 63 ms 1612 KB correct
36 Correct 52 ms 1356 KB correct
37 Correct 8 ms 332 KB correct
38 Correct 59 ms 1632 KB correct
39 Correct 52 ms 1516 KB correct
40 Correct 43 ms 1356 KB correct
41 Correct 57 ms 1632 KB correct
42 Correct 57 ms 1620 KB correct
43 Correct 25 ms 1184 KB correct
44 Correct 20 ms 844 KB correct
45 Correct 22 ms 968 KB correct
46 Correct 18 ms 848 KB correct
47 Correct 10 ms 484 KB correct
48 Correct 3 ms 332 KB correct
49 Correct 5 ms 296 KB correct
50 Correct 10 ms 556 KB correct
51 Correct 28 ms 972 KB correct
52 Correct 20 ms 888 KB correct
53 Correct 18 ms 848 KB correct
54 Correct 30 ms 1100 KB correct
55 Correct 30 ms 972 KB correct
56 Correct 27 ms 972 KB correct
57 Correct 28 ms 972 KB correct
58 Correct 1 ms 204 KB correct
59 Correct 1 ms 204 KB correct
60 Correct 218 ms 4268 KB correct
61 Correct 381 ms 5988 KB correct
62 Correct 420 ms 5956 KB correct
63 Correct 373 ms 5976 KB correct
64 Correct 368 ms 5988 KB correct
65 Correct 378 ms 5996 KB correct
66 Correct 386 ms 5964 KB correct
67 Correct 391 ms 5992 KB correct
68 Correct 377 ms 5944 KB correct
69 Correct 414 ms 5964 KB correct
70 Correct 0 ms 296 KB correct
71 Correct 398 ms 5952 KB correct
72 Correct 402 ms 5956 KB correct
73 Correct 1 ms 204 KB correct
74 Correct 408 ms 5956 KB correct
75 Correct 400 ms 5848 KB correct
76 Correct 145 ms 2476 KB correct
77 Correct 374 ms 5984 KB correct
78 Correct 387 ms 5972 KB correct
79 Correct 389 ms 5968 KB correct
80 Correct 380 ms 5824 KB correct
81 Correct 361 ms 5324 KB correct
82 Correct 376 ms 5836 KB correct
83 Correct 261 ms 3524 KB correct
84 Correct 167 ms 4164 KB correct
85 Correct 140 ms 4036 KB correct
86 Correct 91 ms 2596 KB correct
87 Correct 72 ms 2172 KB correct
88 Correct 58 ms 1568 KB correct
89 Correct 53 ms 1636 KB correct
90 Correct 45 ms 1396 KB correct
91 Correct 17 ms 460 KB correct
92 Correct 11 ms 332 KB correct
93 Correct 136 ms 3928 KB correct
94 Correct 108 ms 2636 KB correct
95 Correct 94 ms 2624 KB correct
96 Correct 50 ms 1456 KB correct
97 Correct 56 ms 1572 KB correct
98 Correct 67 ms 2200 KB correct
99 Correct 56 ms 1572 KB correct
100 Correct 26 ms 660 KB correct
101 Correct 13 ms 332 KB correct
102 Correct 173 ms 3196 KB correct
103 Correct 176 ms 3204 KB correct
104 Correct 183 ms 3160 KB correct
105 Correct 169 ms 3164 KB correct