Submission #119726

#	Time	Username	Problem	Language	Result	Execution time	Memory
119726		thebes	Ancient Books (IOI17_books)	C++14	100 / 100	483 ms	176172 KiB

books

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MN = 1e6+6;
ll n, s, x, id[MN], l[MN], r[MN], a[MN], b[MN], aa[MN], bb[MN], nxt, ans, arr[MN], i, j, par[MN], dist[MN], L=1<<30, R, vs[MN];
vector<int> adj[MN], rev[MN];
deque<int> q;

void dfs(ll n){
    ans += abs(arr[n]-n);
    a[id[n]]=min(a[id[n]],n);
    b[id[n]]=max(b[id[n]],n);
    if(n<=s) aa[id[n]]=max(aa[id[n]],n);
    if(n>=s) bb[id[n]]=min(bb[id[n]],n);
    if(id[arr[n]]) return;
    id[arr[n]]=id[n];
    dfs(arr[n]);
}

ll minimum_walk(vector<int> p,int e){
    n = p.size(); s = e+1;
    for(i=0;i<n;i++) arr[i+1]=p[i]+1;
    for(i=1;i<=n;i++){
        a[i] = bb[i] = 1<<30;
        if(!id[i]){
            id[i] = ++nxt;
            dfs(i);
        }
    }
    for(i=1;i<=nxt;i++){
        if(a[i]==b[i]) continue;
        L = min(L, a[i]);
        R = max(R, b[i]);
        if(a[i]<=s&&s<=b[i]){
            l[a[i]]++; l[b[i]]--;
            l[aa[i]]--; l[s]++;
            r[b[i]]++; r[a[i]]--;
            r[s]++; r[bb[i]]--;
            adj[aa[i]].push_back(bb[i]);
            adj[bb[i]].push_back(aa[i]);
        }
        else{
            l[a[i]]++; l[b[i]]--;
            r[b[i]]++; r[a[i]]--;
        }
    }
    if(R==0) return 0LL;
    for(i=1;i<=n;i++){
        x += l[i];
        if(x) adj[i+1].push_back(i);
    }
    x = 0;
    for(i=n;i>=1;i--){
        x += r[i];
        if(x) adj[i-1].push_back(i);
    }
    memset(dist,-1,sizeof(dist));
    q.push_back(s); dist[s] = 0;
    while(q.size()){
        x = q.front(); q.pop_front();
        if(vs[x]) continue;
        vs[x] = 1;
        for(auto v : adj[x]){
            if(dist[v]==-1||dist[x]<dist[v]){
                dist[v] = dist[x]; par[v] = x;
                q.push_front(v);
            }
        }
        if(x>1&&dist[x-1]==-1){
            dist[x-1] = dist[x]+1; par[x-1] = x;
            q.push_back(x-1);
        }
        if(x<n&&dist[x+1]==-1){
            dist[x+1] = dist[x]+1; par[x+1] = x;
            q.push_back(x+1);
        }
    }
    ans += 2*dist[L];
    memset(dist,-1,sizeof(dist));
    memset(vs,0,sizeof(vs));
    x = L;
    while(1){
        q.push_back(x);
        dist[x] = 0;
        if(!par[x]) break;
        x = par[x];
    }
    while(q.size()){
        x = q.front(); q.pop_front();
        if(vs[x]) continue;
        vs[x] = 1;
        for(auto v : adj[x]){
            if(dist[v]==-1||dist[x]<dist[v]){
                dist[v] = dist[x]; par[v] = x;
                q.push_front(v);
            }
        }
        if(x>1&&dist[x-1]==-1){
            dist[x-1] = dist[x]+1; par[x-1] = x;
            q.push_back(x-1);
        }
        if(x<n&&dist[x+1]==-1){
            dist[x+1] = dist[x]+1; par[x+1] = x;
            q.push_back(x+1);
        }
    }
    ans += 2*dist[R];
    return ans;
}

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