Submission #95259

#	Time	Username	Problem	Language	Result	Execution time	Memory
95259		andy627	Ancient Books (IOI17_books)	C++17	100 / 100	202 ms	46080 KiB

books

#include "books.h"

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <limits.h>
#define LL long long
#define INF INT_MAX
using namespace std;

int cyc_n;
int cyc_idx[1111111];
int cyc_l[1111111],cyc_r[1111111];

int par[1111111];

int cyc_par[1111111];
int cyc_ldist[1111111],cyc_rdist[1111111];
int cyc_dist[1111111];
int cyc_pos[1111111];

int find_(int x) {
    if(par[x]!=x) return par[x]=find_(par[x]);
    return x;
}

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

    LL dist1=0;
    int l=n,r=-1;
    for(int i=0;i<n;i++){
        dist1+=abs(P[i]-i);
        if(P[i]!=i) l=min(l,i),r=max(r,i);
    }

    if(!dist1) return 0;

    for(int i=0;i<n;i++){
        if(cyc_idx[i]){
            cyc_r[cyc_idx[i]]=i;
            continue;
        }

        cyc_idx[i]=++cyc_n;
        par[cyc_idx[i]]=cyc_idx[i];
        cyc_dist[cyc_idx[i]]=INF;
        cyc_l[cyc_idx[i]]=cyc_r[cyc_idx[i]]=i;

        int j=P[i];
        while(i!=j){
            cyc_idx[j]=cyc_idx[i];
            j=P[j];
        }
    }

    vector<int> st;
    for(int i=0;i<n;i++){
        int rt=find_(cyc_idx[i]);
        if(cyc_l[rt]==i) st.push_back(rt);
        if(!st.empty() && st.back()!=rt){
            par[st.back()]=rt;
            cyc_l[rt]=min(cyc_l[rt],cyc_l[st.back()]);
            cyc_r[rt]=max(cyc_r[rt],cyc_r[st.back()]);
            st.pop_back();
        }
        if(cyc_r[rt]==i) st.pop_back();
    }

    for(int i=0;i<n;i++){
        int rt=find_(cyc_idx[i]);
        if(cyc_l[rt]==i){
            if(!st.empty()) cyc_par[rt]=st.back();
            st.push_back(rt);
        }
        if(cyc_r[rt]==i) st.pop_back();
    }

    for(int i=0;i<n;i++){
        int rt=find_(cyc_idx[i]);
        cyc_pos[rt]=i;

        if(cyc_l[rt]==i) cyc_ldist[rt]=i-cyc_pos[cyc_par[rt]];
        cyc_pos[cyc_par[rt]]=max(cyc_pos[cyc_par[rt]],i-cyc_ldist[rt]);
        cyc_pos[rt]=i;
    }

    for(int i=n;i--;){
        int rt=find_(cyc_idx[i]);
        cyc_pos[rt]=i;

        if(cyc_r[rt]==i) cyc_rdist[rt]=cyc_pos[cyc_par[rt]]-i;
        cyc_pos[cyc_par[rt]]=min(cyc_pos[cyc_par[rt]],i+cyc_rdist[rt]);
        cyc_pos[rt]=i;
    }

    int x=-1;
    LL dist2=0;
    for(int i=0;i<n;i++){
        int rt=find_(cyc_idx[i]);
        if(!cyc_par[rt] && cyc_l[rt]==i && cyc_l[rt]!=cyc_r[rt]){
            cyc_dist[rt]=0;

            if(x!=-1) dist2+=cyc_l[rt]-x;
            x=cyc_r[rt];
        }
        else cyc_dist[rt]=min(cyc_ldist[rt],cyc_rdist[rt]);
    }

    LL dist3=0;
    int rt=find_(cyc_idx[s]);
    if(cyc_par[rt]){
        while(cyc_par[rt]){
            dist3+=cyc_dist[rt];
            rt=cyc_par[rt];
        }
    }
    else if(s<l) dist3=l-s;
    else if(r<s) dist3=s-r;

    return dist1+((dist2+dist3)<<1);
}

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