oj.uz

답안 #400969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400969 2021-05-08T22:50:57 Z LucaDantas 고대 책들 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -