oj.uz

Submission #526872

# Submission time Handle Problem Language Result Execution time Memory
526872 2022-02-16T13:13:35 Z KoD Ancient Books (IOI17_books) C++17
50 / 100
 1204 ms 152676 KB 
#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<vector<int>> list(2 * N);
		const auto process = [&](int k, const int i) {
			while (k > 0) {
				for (const int j : list[k]) dsu.merge(i, j);
				list[k] = {i};
				k >>= 1;
			}
		};
		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) {
				const int lc = N + v[j - 1];
				const int rc = N + v[j];
				for (int l = lc, r = rc; l < r; l >>= 1, r >>= 1) {
					if (l & 1) list[l++].push_back(i);
					if (r & 1) list[--r].push_back(i);
				}
				process(lc, i);
				process(rc, 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.0 / 12.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 979 ms 123136 KB Output is correct
31 Correct 1083 ms 128328 KB Output is correct
32 Correct 101 ms 14884 KB Output is correct
33 Correct 583 ms 143364 KB Output is correct
34 Correct 608 ms 143316 KB Output is correct
35 Correct 716 ms 144520 KB Output is correct
36 Correct 979 ms 139228 KB Output is correct
37 Correct 1100 ms 131496 KB Output is correct
38 Correct 1104 ms 130240 KB Output is correct
39 Correct 1115 ms 130084 KB Output is correct
40 Correct 1164 ms 129156 KB Output is correct
41 Correct 1125 ms 128540 KB Output is correct
42 Correct 1204 ms 128772 KB Output is correct
43 Correct 652 ms 152676 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 979 ms 123136 KB Output is correct
31 Correct 1083 ms 128328 KB Output is correct
32 Correct 101 ms 14884 KB Output is correct
33 Correct 583 ms 143364 KB Output is correct
34 Correct 608 ms 143316 KB Output is correct
35 Correct 716 ms 144520 KB Output is correct
36 Correct 979 ms 139228 KB Output is correct
37 Correct 1100 ms 131496 KB Output is correct
38 Correct 1104 ms 130240 KB Output is correct
39 Correct 1115 ms 130084 KB Output is correct
40 Correct 1164 ms 129156 KB Output is correct
41 Correct 1125 ms 128540 KB Output is correct
42 Correct 1204 ms 128772 KB Output is correct
43 Correct 652 ms 152676 KB Output is correct
44 Incorrect 1 ms 332 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
45 Halted 0 ms 0 KB -