Submission #66320

#	Time	Username	Problem	Language	Result	Execution time	Memory
66320		FedericoS	Ancient Books (IOI17_books)	C++14	0 / 100	4 ms	620 KiB

books

#include <iostream>
#include <algorithm>
#include "books.h"
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

int N,S;
int UFp[1000006],UFh[1000006];
ll P[1000006];
int C[1000006];
ll ans;
int c;
ll ult1,ult2=-1;
vector<pll> V;

int UFfind(int k){

    int a;
    for(a=k;a!=UFp[a];a=UFp[a]);

    UFp[k]=a;
    return a;

}

void UFunion(int x, int y){

    x=UFfind(x);
    y=UFfind(y);

    if(UFh[x]<UFh[y])
        swap(x,y);

    UFp[y]=UFp[x];
    UFh[x]=max(UFh[x],UFh[y]+1);

}

long long minimum_walk(std::vector<int> q, int s) {

    N=q.size();
    S=s;
    for(ll i=0;i<N;i++){
        P[i]=q[i];
        ans+=abs(P[i]-i);
    }
    for(int i=0;i<N;i++){
        UFp[i]=i;
        UFh[i]=1;
    }

    fill(C,C+N,-1);

    for(int i=0;i<N;i++)
        if(C[i]==-1 and (i==0 or P[i]!=i)){
            int a=P[i];
            C[i]=c;
            while(a!=i){
                C[a]=c;
                a=P[a];
            }
            c++;
        }

    for(ll i=0;i<N;i++)
        for(ll j=i-1;j>=0;j--)
            if(C[i]!=C[j] and P[i]!=i and (P[j]!=j or j==0)){
                V.push_back({i-j,i});
                break;
            }

    sort(V.begin(),V.end());

    int p=0;
    for(int g=0;g<c-1;g++){
        while(UFfind(V[p].second)==UFfind(V[p].second-V[p].first))
            p++;
        ans+=V[p].first*2;
        UFunion(V[p].second,V[p].second-V[p].first);
    }

    return ans;

}
/*
    for(int i=0;i<N;i++)
        cout<<P[i]<<" "<<C[i]<<endl;
    for(auto p:V)
        cout<<p.first<<" "<<p.second<<" "<<p.second-p.first<<endl;
*/

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