oj.uz

Submission #400969

# Submission time Handle Problem Language Result Execution time Memory
400969 2021-05-08T22:50:57 Z LucaDantas Ancient Books (IOI17_books) C++17
20 / 100
 38 ms 55180 KB 
#include "books.h"
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>

constexpr int maxn = 2e6+10;

int t, comp[maxn], dist[maxn], L[maxn], R[maxn], opa[maxn];
std::vector<std::pair<int,int>> g[maxn];

bool foi[maxn];

void bfs(int s) {
	for(int i = 0; i < maxn; i++)
		dist[i] = maxn;
	std::deque<int> q = {s};
	dist[s] = 0;
	while(q.size()) {
		int u = q.front(); q.pop_front();
		if(foi[u]) continue;
		foi[u] = 1;
		for(auto pp : g[u]) {
			auto [v, w] = pp;
			if(dist[v] <= dist[u] + w) continue;
			dist[v] = dist[u] + w;
			if(w) q.push_back(v);
			else q.push_front(v);
		}
	}
}

void dfs(int u, const std::vector<int>& p, int& fim) {
	fim = std::max(fim, u);
	comp[u] = t;
	if(!comp[p[u]]) dfs(p[u], p, fim);
}

int pai[maxn], n;
bool mark[maxn];

int pr(int u) { return !mark[u] || u==n-1 ? u : pai[u] = pr(pai[u]); }

long long minimum_walk(std::vector<int> p, int s) {
	n = (int)p.size();
	long long ans = 0;

	std::vector<std::pair<int,int>> seg;

	int tot = 0;
	for(int i = 0; i < n; i++) {
		pai[i] = i+1;
		tot = std::max(tot, p[i]);
		opa[i] = tot>i;
		ans += abs(i-p[i]);
		if(!comp[i] && tot > i) {
			int fim = 0; ++t;
			dfs(i, p, fim);
			seg.push_back({i, fim});
			L[t] = i, R[t] = fim;
		}
	}

	std::sort(seg.begin(), seg.end(), [](std::pair<int,int> x, std::pair<int,int> y) {
		return x.second - x.first < y.second - y.first;
	});

	for(std::pair<int,int> p : seg) {
		auto [l, r] = p;
		for(int i = l; i < r; i = pr(i)) {
			if(L[comp[i]] < l || R[comp[i]] > r)
				g[comp[l]].push_back({comp[i], 0}), g[comp[i]].push_back({comp[l], 0});
			mark[i] = 1;
		}
		mark[l] = mark[r] = 0;
	}

	for(int i = 1; i < n; i++) if(opa[i-1] && comp[i] != comp[i-1])
		g[comp[i]].push_back({comp[i-1], 1}), g[comp[i-1]].push_back({comp[i], 1});


	if(comp[s]) {
		bfs(comp[s]);
		for(int i = 1; i <= t; i++)
			if(dist[i] < maxn) { ans += dist[i]<<1; break; }
	}

	int cnt = 0;
	for(int i = s; i >= 0; i--)
		if(!opa[i]) ++cnt;
		else ans += cnt<<1, cnt = 0;

	cnt = 0;
	for(int i = s+1; i < n; i++)
		if(!opa[i]) ++cnt;
		else ans += cnt<<1, cnt = 0;

	return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55116 KB Output is correct
2 Correct 37 ms 55128 KB Output is correct
3 Correct 34 ms 55068 KB Output is correct
4 Correct 27 ms 47276 KB Output is correct
5 Correct 32 ms 55116 KB Output is correct
6 Correct 33 ms 55124 KB Output is correct
7 Correct 33 ms 55108 KB Output is correct
8 Correct 32 ms 55100 KB Output is correct
9 Correct 32 ms 55108 KB Output is correct
10 Correct 25 ms 47180 KB Output is correct
11 Correct 33 ms 55144 KB Output is correct
12 Correct 32 ms 55104 KB Output is correct
13 Correct 33 ms 55132 KB Output is correct
14 Correct 34 ms 55064 KB Output is correct
15 Correct 38 ms 55116 KB Output is correct
16 Correct 32 ms 55116 KB Output is correct
17 Correct 32 ms 55180 KB Output is correct
18 Correct 32 ms 55076 KB Output is correct
19 Correct 32 ms 55064 KB Output is correct
20 Correct 32 ms 55168 KB Output is correct

Subtask #5
0 / 30.0

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