oj.uz

Submission #33946

# Submission time Handle Problem Language Result Execution time Memory
33946 2017-11-05T11:34:37 Z imeimi2000 Ancient Books (IOI17_books) C++14
12 / 100
 0 ms 27320 KB 
#include "books.h"
#include <algorithm>

using namespace std;
typedef long long llong;

const int max_n = 1e6;
const int max_cycle = max_n / 2 + 1;
int n;
int cycle[max_cycle + 1];
int cycle_l[max_cycle + 1];
int cycle_r[max_cycle + 1];
int group_par[max_cycle + 1];
int cycle_n = 0;

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

int find(int x) {
	if (uf[x]) 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 (cycle_l[c] < cycle_l[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) {
		if (group_par[i] != 0) 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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27320 KB Output is correct
2 Correct 0 ms 27320 KB Output is correct
3 Correct 0 ms 27320 KB Output is correct
4 Correct 0 ms 27320 KB Output is correct
5 Correct 0 ms 27320 KB Output is correct
6 Correct 0 ms 27320 KB Output is correct
7 Correct 0 ms 27320 KB Output is correct
8 Correct 0 ms 27320 KB Output is correct
9 Correct 0 ms 27320 KB Output is correct
10 Correct 0 ms 27320 KB Output is correct
11 Correct 0 ms 27320 KB Output is correct
12 Correct 0 ms 27320 KB Output is correct
13 Correct 0 ms 27320 KB Output is correct
14 Correct 0 ms 27320 KB Output is correct
15 Correct 0 ms 27320 KB Output is correct
16 Correct 0 ms 27320 KB Output is correct
17 Correct 0 ms 27320 KB Output is correct
18 Correct 0 ms 27320 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27320 KB Output is correct
2 Correct 0 ms 27320 KB Output is correct
3 Correct 0 ms 27320 KB Output is correct
4 Correct 0 ms 27320 KB Output is correct
5 Correct 0 ms 27320 KB Output is correct
6 Correct 0 ms 27320 KB Output is correct
7 Correct 0 ms 27320 KB Output is correct
8 Correct 0 ms 27320 KB Output is correct
9 Correct 0 ms 27320 KB Output is correct
10 Correct 0 ms 27320 KB Output is correct
11 Correct 0 ms 27320 KB Output is correct
12 Correct 0 ms 27320 KB Output is correct
13 Correct 0 ms 27320 KB Output is correct
14 Correct 0 ms 27320 KB Output is correct
15 Correct 0 ms 27320 KB Output is correct
16 Correct 0 ms 27320 KB Output is correct
17 Correct 0 ms 27320 KB Output is correct
18 Correct 0 ms 27320 KB Output is correct
19 Incorrect 0 ms 27320 KB 3rd lines differ - on the 1st token, expected: '338572', found: '336580'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27320 KB Output is correct
2 Correct 0 ms 27320 KB Output is correct
3 Correct 0 ms 27320 KB Output is correct
4 Correct 0 ms 27320 KB Output is correct
5 Correct 0 ms 27320 KB Output is correct
6 Correct 0 ms 27320 KB Output is correct
7 Correct 0 ms 27320 KB Output is correct
8 Correct 0 ms 27320 KB Output is correct
9 Correct 0 ms 27320 KB Output is correct
10 Correct 0 ms 27320 KB Output is correct
11 Correct 0 ms 27320 KB Output is correct
12 Correct 0 ms 27320 KB Output is correct
13 Correct 0 ms 27320 KB Output is correct
14 Correct 0 ms 27320 KB Output is correct
15 Correct 0 ms 27320 KB Output is correct
16 Correct 0 ms 27320 KB Output is correct
17 Correct 0 ms 27320 KB Output is correct
18 Correct 0 ms 27320 KB Output is correct
19 Incorrect 0 ms 27320 KB 3rd lines differ - on the 1st token, expected: '338572', found: '336580'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 27320 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2746'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27320 KB Output is correct
2 Correct 0 ms 27320 KB Output is correct
3 Correct 0 ms 27320 KB Output is correct
4 Correct 0 ms 27320 KB Output is correct
5 Correct 0 ms 27320 KB Output is correct
6 Correct 0 ms 27320 KB Output is correct
7 Correct 0 ms 27320 KB Output is correct
8 Correct 0 ms 27320 KB Output is correct
9 Correct 0 ms 27320 KB Output is correct
10 Correct 0 ms 27320 KB Output is correct
11 Correct 0 ms 27320 KB Output is correct
12 Correct 0 ms 27320 KB Output is correct
13 Correct 0 ms 27320 KB Output is correct
14 Correct 0 ms 27320 KB Output is correct
15 Correct 0 ms 27320 KB Output is correct
16 Correct 0 ms 27320 KB Output is correct
17 Correct 0 ms 27320 KB Output is correct
18 Correct 0 ms 27320 KB Output is correct
19 Incorrect 0 ms 27320 KB 3rd lines differ - on the 1st token, expected: '338572', found: '336580'
20 Halted 0 ms 0 KB -