Submission #432669

#	Time	Username	Problem	Language	Result	Execution time	Memory
432669		KoD	Simurgh (IOI17_simurgh)	C++17	100 / 100	420 ms	5996 KiB

simurgh

#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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30