제출 #585701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585701		InternetPerson10	Ancient Books (IOI17_books)	C++17	0 / 100	1 ms	340 KiB

books

#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

vector<vector<int>> adj;
vector<int> dist;

long long minimum_walk(vector<int> p, int s) {
    ll tot = 0;
    int n = p.size();
    vector<bool> taken(n, false);
    int g = n;
    adj.resize(n);
    for(int i = 1; i < n; i++) {
        adj[i].push_back(i-1);
        adj[i-1].push_back(i);
    }
    for(int i = 0; i < n; i++) {
        if(!taken[i]) {
            adj.push_back(vector<int>());
            int x = i;
            int l = i, r = i;
            while(!taken[x]) {
                taken[x] = true;
                tot += abs(x - p[x]);
                x = p[x];
                l = min(l, x);
                r = max(r, x);
                adj[x].push_back(g);
            }
            for(int j = l; j <= r; j++) {
                adj[g].push_back(j);
            }
            g++;
        }
    }
    dist.resize(g, 1e9 + 7);
    int best = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while(pq.size()) {
        auto p = pq.top();
        pq.pop();
        int len = p.first, x = p.second;
        if(len > dist[x]) continue;
        best = max(best, len);
        for(int ch : adj[x]) {
            int goLength;
            if(max(ch, x) < n) {
                goLength = len + 1;
            }
            else {
                goLength = len;
            }
            if(dist[ch] <= goLength) continue;
            dist[ch] = goLength;
            pq.push({goLength, ch});
        }
    }
	return tot + 2 * best;
}

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