제출 #137757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137757		ckodser	Ancient Books (IOI17_books)	C++14	100 / 100	1380 ms	168292 KiB

books

#include "books.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e6+500;
const ll inf=1e9+900;
const ll logg=20;

vector<ll> p;
bool vis[maxn];
ll d[maxn];

ll last=-1,fir,N;
ll cnt=0;
ll mxx[maxn];
ll mnn[maxn];

ll l[maxn];
ll r[maxn];

map<pii,ll> ml;
ll ras[maxn];
vector<pii> ger[maxn];
ll fas[maxn];

void addYal(ll a,ll b,ll w){
    ger[a].pb(mp(b,w));
}
void bfs(ll a){
    fill(fas,fas+maxn,inf);
    deque<ll> qu;
    qu.pb(a);
    fas[a]=0;
    while(qu.size()){
	ll v=qu.back();
	qu.pop_back();
	for(auto e:ger[v]){
	    if(fas[e.F]==inf){
		fas[e.F]=fas[v]+e.S;
		if(e.S==0){
		    qu.pb(e.F);
		}else{
		    qu.push_front(e.F);
		}
	    }			
	}
    }
}


void dfs(ll a){
    if(vis[a])return;
    vis[a]=2;
    d[a]=cnt;
    dfs(p[a]);
}
long long minimum_walk(vector<int> P, int s){
    p=P;
    ll n=p.size();
    N=n;
    long long ans=0;
    for(ll i=0;i<n;i++){
	if(!vis[i]){
	    dfs(i);
	    cnt++;
	}
	if(p[i]!=i)last=i;
	ans+=abs(i-p[i]);
    }
    for(ll i=n-1;i>=0;i--){
	if(p[i]!=i){
	    fir=i;
	}
    }
    if(last==-1)return 0;
    fill(mnn,mnn+maxn,inf);
    fill(mxx,mxx+maxn,0);

    for(ll i=0;i<n;i++){
	mnn[d[i]]=min(mnn[d[i]],i);
	mxx[d[i]]=max(mxx[d[i]],i);
    }
    if(s<=fir){
	ll t=s;
	for(ll i=s;i<=last;i++){
	    if(t<i){
		ans+=2;
		t=max(t,i);
	    }
	    t=max(t,mxx[d[i]]);
	}
	return ans;
    }
    if(s>=last){
   	ll t=s;
	for(ll i=s;i>=fir;i--){
	    if(i<t){
		ans+=2;
		t=min(t,i);
	    }
	    t=min(t,mnn[d[i]]);
	}
	return ans;
    }
    ll minn,maxx;
    minn=fir;
    maxx=fir;
    for(ll i=fir;i<s;i++){
	minn=min(minn,mnn[d[i]]);
	maxx=max(maxx,mxx[d[i]]);
	if(maxx==i){
	    ans+=2;
	    fir=i+1;
	}
    }
    minn=last;
    maxx=last;
    for(ll i=last;i>s;i--){
	minn=min(minn,mnn[d[i]]);
	maxx=max(maxx,mxx[d[i]]);
	if(minn==i){
	    ans+=2;
	    last=i-1;
	}
    }
    minn=s;
    maxx=s;
    for(ll i=s;i<n;i++){
	minn=min(minn,mnn[d[i]]);
	maxx=max(maxx,mxx[d[i]]);
	l[i]=minn;
	r[i]=maxx;
    }
    minn=s;
    maxx=s;
    for(ll i=s;i>=0;i--){
	minn=min(minn,mnn[d[i]]);
	maxx=max(maxx,mxx[d[i]]);
	l[i]=minn;
	r[i]=maxx;
    }
    for(ll i=0;i<n;i++){
	l[i]=max(l[i],fir);
	r[i]=min(r[i],last);
    }
    cnt=0;
    for(ll i=fir;i<=last;i++){
	if(ml.count(mp(l[i],r[i]))==0){
	    ml[mp(l[i],r[i])]=cnt++;
	}
	ras[i]=ml[mp(l[i],r[i])];
    }
    ll start=ras[s];
    for(ll i=fir;i<=last;i++){
	ll v=ml[mp(l[i],r[i])];
	addYal(v,ras[l[i]],0);
	addYal(v,ras[r[i]],0);
	if(i!=fir){
	    addYal(v,ras[i-1],1);
	}
	if(i!=last){
	    addYal(v,ras[i+1],1);
	}
    }
    bfs(start);
    ll res=min(fas[ras[fir]],fas[ras[last]]);
    return ans+res*2;
}

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