Submission #1199858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199858		Hanksburger	Ancient Books (IOI17_books)	C++17	100 / 100	427 ms	211004 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll comp[1000005], l[1000005], r[1000005], dist[1000005], final[1000005], visited[1000005], n, cnt;
vector<pair<ll, ll> > adj[1000005], revadj[1000005], v;
priority_queue<pair<ll, ll> > pq;
stack<ll> ss;
queue<ll> q;
ll minimum_walk(vector<int> a, int s)
{
    ll n=a.size(), cnt=0, ans=0;
    for (ll i=0; i<n; i++)
    {
        ans+=abs(a[i]-i);
        if (comp[i] || (i!=s && a[i]==i))
            continue;
        cnt++;
        l[cnt]=i;
        ll cur=i;
        while (!comp[cur])
        {
            comp[cur]=cnt;
            r[cnt]=max(r[cnt], cur);
            cur=a[cur];
        }
    }
    ll L=1e18, R=0;
    for (ll i=0; i<n; i++)
    {
        if (!comp[i])
            continue;
        L=min(L, i);
        R=max(R, r[comp[i]]);
        if (R==i)
        {
            v.push_back({L, R});
            //cout << "L R " << L << ' ' << R << '\n';
            L=1e18, R=0;
        }
    }
    for (ll i=1; i<v.size(); i++)
        ans+=(v[i].first-v[i-1].second)*2;
    ll ind;
    for (ll i=0; i<v.size(); i++)
    {
        if (v[i].first<=s && s<=v[i].second)
        {
            ind=i;
            break;
        }
    }
    //cout << "ind=" << ind << '\n';
    ll pre=-1;
    for (ll i=0; i<n; i++)
    {
        if (!comp[i])
            continue;
        if (pre!=-1 && comp[pre]!=comp[i])
        {
            adj[comp[pre]].push_back({comp[i], i-pre});
            revadj[comp[i]].push_back({comp[pre], i-pre});
        }
        pre=i;
    }
    pre=-1;
    for (ll i=n-1; i>=0; i--)
    {
        if (!comp[i])
            continue;
        if (pre!=-1 && comp[pre]!=comp[i])
        {
            adj[comp[pre]].push_back({comp[i], pre-i});
            revadj[comp[i]].push_back({comp[pre], pre-i});
        }
        pre=i;
    }
    for (ll i=0; i<n; i++)
    {
        if (!comp[i])
            continue;
        if (ss.size() && comp[ss.top()]!=comp[i])
        {
            adj[comp[ss.top()]].push_back({comp[i], 0});
            revadj[comp[i]].push_back({comp[ss.top()], 0});
        }
        if (i<r[comp[i]])
            ss.push(i);
        while (ss.size() && r[comp[ss.top()]]<=i)
            ss.pop();
    }
    for (ll i=n-1; i>=0; i--)
    {
        if (!comp[i])
            continue;
        if (ss.size() && comp[ss.top()]!=comp[i])
        {
            adj[comp[ss.top()]].push_back({comp[i], 0});
            revadj[comp[i]].push_back({comp[ss.top()], 0});
        }
        if (i>l[comp[i]])
            ss.push(i);
        while (ss.size() && l[comp[ss.top()]]>=i)
            ss.pop();
    }
    /*for (ll i=1; i<=cnt; i++)
    {
        cout << "edges: ";
        for (int j=0; j<adj[i].size(); j++)
            cout << adj[i][j].first << ' ' << adj[i][j].second << ' ';
        cout << '\n';
    }*/
    for (ll i=1; i<=cnt; i++)
        dist[i]=1e18;
    dist[comp[s]]=0;
    pq.push({0, comp[s]});
    while (!pq.empty())
    {
        ll u=pq.top().second;
        pq.pop();
        if (final[u])
            continue;
        final[u]=1;
        for (ll i=0; i<adj[u].size(); i++)
        {
            ll v=adj[u][i].first, w=adj[u][i].second;
            if (dist[u]+w<dist[v])
            {
                dist[v]=dist[u]+w;
                pq.push({-dist[v], v});
            }
        }
    }
    visited[comp[v[ind].first]]=1;
    q.push(comp[v[ind].first]);
    while (!q.empty())
    {
        ll u=q.front();
        q.pop();
        for (ll i=0; i<revadj[u].size(); i++)
        {
            ll v=revadj[u][i].first, w=revadj[u][i].second;
            if (!w && !visited[v])
            {
                visited[v]=1;
                q.push(v);
            }
        }
    }
    ll mn=1e18;
    for (ll i=1; i<=cnt; i++)
        if (visited[i])
            mn=min(mn, dist[i]);
    return ans+mn*2;
}

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