Submission #33957

#	Time	Username	Problem	Language	Result	Execution time	Memory
33957		imeimi2000	Ancient Books (IOI17_books)	C++14	100 / 100	243 ms	40248 KiB

books

#include "books.h"
#include <algorithm>

using namespace std;
typedef long long llong;

const int max_n = 1000000;
const int max_cycle = 500001;
int n;
int cycle[max_n];
int cycle_l[max_cycle];
int cycle_r[max_cycle];
int group_par[max_cycle];
int cycle_n = 0;

int uf[max_cycle];
llong near[max_cycle];
llong go_left[max_cycle];
llong go_right[max_cycle];
llong go[max_cycle];

int find(int x) {
	if (uf[x]) return uf[x] = find(uf[x]);
	return x;
}

long long minimum_walk(vector<int> p, int s) {
	llong dist1 = 0ll;
	n = p.size();
	for (int i = 0; i < n; ++i) {
		dist1 += abs(p[i] - i);
		if (p[i] != i && cycle[i] == 0) {
			cycle[i] = ++cycle_n;
			cycle_l[cycle[i]] = i;
			cycle_r[cycle[i]] = i;
			int j = p[i];
			while (i != j) {
				cycle[j] = cycle[i];
				cycle_r[cycle[i]] = max(cycle_r[cycle[i]], j);
				j = p[j];
			}
		}
	}
	if (dist1 == 0ll) return 0ll;

	vector<int> st;
	st.push_back(0);
	for (int i = 0; i < n; ++i) {
		if (p[i] != i) {
			if (cycle_l[cycle[i]] == i) st.push_back(cycle[i]);
			else {
				int c = find(cycle[i]);
				while (c < st.back()) {
					int x = st.back();
					st.pop_back();
					uf[x] = c;
					cycle_r[c] = max(cycle_r[c], cycle_r[x]);
				}
				if (cycle_r[c] == i) {
					st.pop_back();
					group_par[c] = st.back();
				}
			}
		}
	}

	bool contain = false;
	int right_cycle = 0;
	llong dist2 = 0ll;
	int l = n + 1, r = -1;
	for (int i = 1; i <= cycle_n; ++i) {
		group_par[i] = find(group_par[i]);
		if (find(i) == i) {
			l = min(l, cycle_l[i]);
			r = max(r, cycle_r[i]);
			if (cycle_l[i] < s && s < cycle_r[i]) contain = 1;
			if (right_cycle != 0 && cycle_r[i] < cycle_r[right_cycle]) continue;
			if (right_cycle != 0) dist2 += cycle_l[i] - cycle_r[right_cycle];
			right_cycle = i;
		}
	}

	if (!contain && l <= s && s <= r) return dist1 + dist2 * 2;
	for (int i = 0; i < n; ++i) {
		if (p[i] != i) {
			int c = find(cycle[i]);
			near[c] = i;
			if (group_par[c] != 0 && cycle_l[c] == i)
				go_left[c] = i - near[group_par[c]];
			else if (cycle_r[c] == i)
				near[group_par[c]] = max(near[group_par[c]], i - go_left[c]);
		}
	}
	for (int i = n; i--;) {
		if (p[i] != i) {
			int c = find(cycle[i]);
			near[c] = i;
			if (group_par[c] != 0 && cycle_r[c] == i)
				go_right[c] = near[group_par[c]] - i;
			else if (cycle_l[c] == i)
				near[group_par[c]] = min(near[group_par[c]], i + go_right[c]);
		}
	}

	for (int i = 1; i <= cycle_n; ++i)
		go[i] = min(go_left[i], go_right[i]) + go[group_par[i]];

	llong dist3 = 1e18;
	for (int i = 0; i < n; ++i) {
		if (p[i] != i)
			dist3 = min(go[find(cycle[i])] + abs(i - s), dist3);
	}
	return dist1 + (dist2 + dist3) * 2;
}

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