Submission #370992

#	Time	Username	Problem	Language	Result	Execution time	Memory
370992		KoD	Simurgh (IOI17_simurgh)	C++17	51 / 100	331 ms	4712 KiB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

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

Vec<int> find_roads(int n, Vec<int> U, Vec<int> V) {
	Vec<Vec<std::pair<int, int>>> graph(n);
	const int m = (int) U.size();
	for (int i = 0; i < m; ++i) {
		graph[U[i]].emplace_back(V[i], i);
		graph[V[i]].emplace_back(U[i], i);
	}
	Vec<char> visited(n);
	Vec<int> depth(n), pedge(n, -1);
	Vec<int> edges;
	std::set<int> tree;
	auto dfs = [&](auto dfs, const int u) -> void {
		visited[u] = true;
		for (const auto [v, e]: graph[u]) {
			if (visited[v]) {
				if (depth[u] + 1 < depth[v]) {
					edges.push_back(e);
				}
			}
			else {
				depth[v] = depth[u] + 1;
				pedge[v] = e;
				tree.insert(e);
				dfs(dfs, v);
			}
		}
	};
	dfs(dfs, 0);
	for (int i = 0; i < m; ++i) {
		if (depth[U[i]] > depth[V[i]]) {
			std::swap(U[i], V[i]);
		}
	}
	Vec<char> state(m, 2);
	const auto ask = [&] {
		return count_common_roads(Vec<int>(tree.begin(), tree.end()));
	};
	const auto exchange = [&](const int f, const int e) {
		tree.erase(f);
		tree.insert(e);
		const auto ret = ask();
		tree.insert(f);
		tree.erase(e);
		return ret;
	};	
	const auto base = ask();
	for (const auto e: edges) {
		int X = U[e], Y = V[e];
		Vec<int> ok, ng;
		while (Y != X) {
			const auto f = pedge[Y];
			(state[f] == 2 ? ok : ng).push_back(f);
			Y = U[f];
		}
		Vec<int> same, differ;
		for (const auto f: ok) {
			const auto tmp = exchange(f, e);
			if (tmp < base) {
				state[e] = 0;
				differ.push_back(f);
			}
			else if (tmp > base) {
				state[e] = 1;
				differ.push_back(f);
			}
			else {
				same.push_back(f);
			}
		}
		if (state[e] == 2) {
			if (ng.empty()) {
				state[e] = 0;
			}
			else {
				const auto f = ng.front();
				if (base == exchange(f, e)) {
					state[e] = state[f];
				}
				else {
					state[e] = 1 - state[f];
				}
			}
		}
		for (const auto f: same) {
			state[f] = state[e];
		}
		for (const auto f: differ) {
			state[f] = 1 - state[e];
		}
	}
	Vec<int> ret;
	for (int i = 0; i < m; ++i) {
		if (state[i] != 0) {
			ret.push_back(i);
		}
	}
	return ret;
}		

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30