제출 #526341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526341		leaked	고대 책들 (IOI17_books)	C++14	22 / 100	2066 ms	46052 KiB

books

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


#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m_p make_pair
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
//#define pragma optimize("unroll-loops")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int N=1e6+3;
struct dsu{
    int p[N],sz[N];
    void make(int v){
        p[v]=v;
        sz[v]=1;
    }
    void init(){
        for(int i=0;i<N;i++)
            make(i);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    bool mg(int a,int b){
        a=get(a),b=get(b);
        if(a==b) return 0;
        if(sz[a]>sz[b]) swap(a,b);
        p[a]=b;sz[b]+=sz[a];
        return 1;
    }
}ds;
long long minimum_walk(std::vector<int> p, int s) {
    ds.init();
    int n=sz(p);
    vec<int>used(n,0);
    vec<int>rgt(n,0);
    ll ans=0;
    vec<pii> arr;
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        int j=i;
        vec<int>vc;
        while(!used[j]){
            used[j]=1;
            vc.pb(j);
            ans+=abs(p[j]-j);
            j=p[j];
        }
        int mx=*max_element(all(vc));
        for(auto &z : vc){
            rgt[z]=mx;
        }
        if(sz(vc)==1) {cerr<<"J "<<i<<endl;continue;}
        arr.pb({i,mx});
//        cout<<"HEY "<<endl;
////        for(auto &z : vc)
//            cout<<z<<' ';
//        cout<<endl;
    }
    vec<pii> narr;
    for(auto &z : arr){
        if(!sz(narr) || narr.back().s<z.f) narr.pb(z);
        else umax(narr.back().s,z.s);
    }
    swap(arr,narr);
    vec<int> incomp(n,-1);
    int j=0;
    for(auto &z : arr){
        for(int i=z.f;i<=z.s;i++){
            if(p[i]!=i) incomp[i]=j;
        }
        j++;
    }
    vec<array<int,3>> e;

    for(int i=0;i<n;i++){
        if(incomp[i]!=-1){
            e.pb({2*abs(s-i),incomp[i],n});
        }
    }
    ds.init();
//    for(int i=0;i<sz(arr);i++){
//        e.pb({2*min(abs(s-arr[i].f),abs(s-arr[i].s)),i,n});
////        cout<<"I "<<i<<' '<<arr[i].f<<' '<<arr[i].s<<endl;
//    }
    for(int i=1;i<sz(arr);i++){
        e.pb({2*abs(arr[i].f-arr[i-1].s),i,i-1});
    }
    sort(all(e));
    for(auto &z : e){
//        cout<<"Z "<<z[0]<<' '<<z[1]<<' '<<z[2];
        if(ds.mg(z[1],z[2]))
            ans+=z[0];
    }
	return ans;
}

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