Submission #1199425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199425		Hanksburger	Ancient Books (IOI17_books)	C++17	0 / 100	0 ms	328 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<pair<ll, pair<ll, ll> > > edges;
ll comp[1000005], sz[1000005], par[1000005], n, cnt, ind=-1, ans;
ll findPar(ll u)
{
    return par[u]==u?u:par[u]=findPar(par[u]);
}
ll minimum_walk(vector<int> a, int s)
{
    n=a.size();
    for (ll i=0; i<n; i++)
    {
        ans+=abs(a[i]-i);
        if (comp[i] || (i!=s && a[i]==i))
            continue;
        cnt++;
        ll cur=i;
        while (!comp[cur])
        {
            comp[cur]=cnt;
            sz[cnt]++;
            cur=a[cur];
        }
    }
    for (ll i=0; i<n; i++)
    {
        if (!comp[i])
            continue;
        if (ind!=-1 && comp[ind]!=comp[i])
            edges.push_back({i-ind, {comp[ind], comp[i]}});
        ind=i;
    }
    sort(edges.begin(), edges.end());
    for (ll i=1; i<=cnt; i++)
        par[i]=i;
    for (auto edge:edges)
    {
        ll u=edge.second.first, v=edge.second.second, w=edge.first;
        if (findPar(u)!=findPar(v))
        {
            ans+=w*2;
            par[findPar(u)]=findPar(v);
        }
    }
    return ans;
}

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