oj.uz

Submission #432655

# Submission time Handle Problem Language Result Execution time Memory
432655 2021-06-18T12:07:49 Z KoD Simurgh (IOI17_simurgh) C++17
30 / 100
 206 ms 3724 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()));
	int qcnt = 1;
	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()));
				qcnt += 1;
				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()));
				qcnt += 1;
				tree.erase(e);
				tree.insert(f);
				type[e] = type[f] * (tmp == tree_cnt ? 0 : -1);
			}
		}
		for (const int f : same) {
			type[f] = type[e];
		}
		for (const int f : dif) {
			type[f] = type[e] * -1;
		}
	}
	assert(qcnt <= 1500);
	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 1 ms 204 KB correct
5 Correct 1 ms 204 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 204 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 1 ms 204 KB correct
5 Correct 1 ms 204 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 204 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 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 3 ms 332 KB correct
18 Correct 2 ms 224 KB correct
19 Correct 3 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 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 204 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 204 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 204 KB correct
33 Correct 1 ms 292 KB correct

Subtask #3
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 1 ms 204 KB correct
5 Correct 1 ms 204 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 204 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 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 3 ms 332 KB correct
18 Correct 2 ms 224 KB correct
19 Correct 3 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 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 204 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 204 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 204 KB correct
33 Correct 1 ms 292 KB correct
34 Runtime error 63 ms 2720 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 206 ms 3724 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
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 1 ms 204 KB correct
5 Correct 1 ms 204 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 204 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 332 KB correct
15 Correct 2 ms 332 KB correct
16 Correct 2 ms 332 KB correct
17 Correct 3 ms 332 KB correct
18 Correct 2 ms 224 KB correct
19 Correct 3 ms 332 KB correct
20 Correct 2 ms 332 KB correct
21 Correct 3 ms 332 KB correct
22 Correct 1 ms 332 KB correct
23 Correct 1 ms 332 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 204 KB correct
28 Correct 1 ms 204 KB correct
29 Correct 1 ms 204 KB correct
30 Correct 1 ms 204 KB correct
31 Correct 1 ms 204 KB correct
32 Correct 1 ms 204 KB correct
33 Correct 1 ms 292 KB correct
34 Runtime error 63 ms 2720 KB Execution killed with signal 6
35 Halted 0 ms 0 KB -