Submission #526878

#	Time	Username	Problem	Language	Result	Execution time	Memory
526878		KoD	Ancient Books (IOI17_books)	C++17	100 / 100	810 ms	208124 KiB

books

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

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

struct UnionFind {
	vector<int> par;
	UnionFind(const int n) : par(n, -1) {}
	int find(const int u) {
		return par[u] < 0 ? u : par[u] = find(par[u]);
	}
	void merge(int u, int v) {
		u = find(u), v = find(v);
		if (u == v) return;
		if (par[u] > par[v]) std::swap(u, v);
		par[u] += par[v];
		par[v] = u;
		return;
	}
};

ll minimum_walk(vector<int> P, int src) {
	{
		int l = 0;
		while (l < src and P[l] == l) l += 1;
		int r = (int)P.size() - 1;
		while (r > src and P[r] == r) r -= 1;
		P.erase(P.begin() + r + 1, P.end());
		P.erase(P.begin(), P.begin() + l);
		for (auto& x : P) x -= l;
		src -= l;
	}
	const int N = P.size();
	vector<vector<int>> cycle;
	{
		vector<char> done(N);
		for (int i = 0; i < N; ++i) {
			if (done[i]) continue;
			auto& v = cycle.emplace_back();
			for (int j = i; !done[j]; j = P[j]) {
				v.push_back(j);
				done[j] = true;
			}
		}
	}
	const int M = cycle.size();
	UnionFind dsu(M);
	{
		vector<tuple<int, int, int>> query;
		for (int i = 0; i < M; ++i) {
			auto& v = cycle[i];
			std::sort(v.begin(), v.end());
			for (int j = 1; j < (int)v.size(); ++j) {
				query.emplace_back(N + v[j - 1], N + v[j], i);
			}
		}
		std::sort(query.begin(), query.end());
		vector<vector<int>> list(2 * N);
		const auto process = [&](const int k, const int i) {
			for (const int j : list[k]) dsu.merge(i, j);
			// list[k] = {i};
		};
		for (const auto& [lc, rc, i] : query) {
			for (int l = lc, r = rc; l < r; l >>= 1, r >>= 1) {
				if (l & 1) process(l++, i);
				if (r & 1) process(--r, i);
			}
			for (int k = rc; k > 0; k >>= 1) list[k].push_back(i);
		}
	}
	vector<int> belongs(N);
	for (int i = 0; i < M; ++i) {
		const int p = dsu.find(i);
		for (const int j : cycle[i]) {
			belongs[j] = p;
		}
	}
	vector<vector<int>> list(M);
	for (int i = 0; i < N; ++i) list[belongs[i]].push_back(i);
	vector<int> parent(M, -1);
	{
		vector<int> start(N, -1), end(N, -1);
		for (int j = 0; j < M; ++j) {
			if (!list[j].empty()) {
				start[list[j].front()] = j;
				end[list[j].back()] = j;
			}
		}
		vector<int> stack;
		for (int i = 0; i < N; ++i) {
			if (start[i] != -1) {
				if (!stack.empty()) parent[start[i]] = stack.back();
				stack.push_back(start[i]);
			}
			if (end[i] != -1) stack.pop_back();
		}
	}
	vector<int> dist(M, N + 1);
	{
		std::queue<int> que;
		const auto push = [&](const int u, const int d) {
			if (dist[u] > d) {
				dist[u] = d;
				que.push(u);
			}
		};
		push(belongs[src], 0);
		while (!que.empty()) {
			const int u = que.front();
			que.pop();
			const int l = list[u].front();
			const int r = list[u].back();
			if (l > 0) push(belongs[l - 1], dist[u] + 1);
			if (r + 1 < N) push(belongs[r + 1], dist[u] + 1);
		}
	}
	int root = belongs[src];
	while (parent[root] != -1) root = parent[root];
	ll ret = 2 * dist[root];
	vector<int> coeff(N);
	for (int i = 0; i < N; ++i) {
		const int l = std::min(i, P[i]);	
		const int r = std::max(i, P[i]);	
		ret += r - l;
		coeff[l] += 1;
		coeff[r] -= 1;
	}
	for (int i = 0; i < N - 1; ++i) {
		if (coeff[i] == 0) ret += 2;
		coeff[i + 1] += coeff[i];
	}
	return ret;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30