제출 #355042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
355042		amunduzbaev	Ancient Books (IOI17_books)	C++14	12 / 100	4 ms	4352 KiB

books

#include "books.h"

#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second

const int N = 1e6+5;
const int mod = 1e9+7;

int n, sz;
int par[N], used[N], pp[N], l[N], r[N];
ll sum[N];

int f(int x){
	if(par[x] == x) return x;
	return par[x] = f(par[x]);
}

void merge(int a, int b){
	a = f(a), b = f(b);
	if(a == b) return;
	l[a] = min(l[b], l[a]);
	r[a] = max(r[a], r[b]);
	par[b] = a;
	sum[a] += sum[b];
}

void dfs(int u){
	//cout<<u<<" ";
	if(used[u]) return;
	used[u] = 1;
	l[f(u)] = min(l[f(u)], pp[u]);
	r[f(u)] = max(r[f(u)], pp[u]);
	par[pp[u]] = f(u);
	//cout<<sum[f(u)]<<" ";
	sum[f(u)] += abs(pp[u] - u);
	//cout<<sum[f(u)]<<"\n";
	dfs(pp[u]);
}

bool cmp(pair<pii, int> A, pair<pii, int> B){
	pii a = A.ff, b = B.ff;
	if(a.ff != b.ff) return a.ff < b.ff;
	return a.ss > b.ss;
}

ll minimum_walk(vector<int> p, int s) {
	n = sz(p);
	//assert(n <= 1000);
	memset(used, 0, sizeof used);
	for(int i=0;i<n;i++){
		par[i] = i, sum[i] = 0, l[i] = i, r[i] = i;
	}
	
	for(int i=0;i<n;i++) pp[i] = p[i];
	vector<pair<pii, int>>  vv;
	//cout<<"here";
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		//cout<<i<<" ";
		dfs(i);
		//cout<<"\n";
		if(l[f(i)] != r[f(i)] || i == s)
		vv.pb({{ l[ f(i) ], r[ f(i) ] }, f(i)});
		//cout<<l[f(i)]<<" "<<r[f(i)]<<"\n";
	}
	
	sort(vv.begin(), vv.end(), cmp);
	
	//for(auto x:vv) cout<<x.ff.ff<<" "<<x.ff.ss<<" "<<x.ss<<"\n";
	
	ll tmp = 0;
	
	for(int i=1; i<sz(vv); i++){
		if(vv[i].ff.ff < vv[i-1].ff.ss) merge(vv[i].ss, vv[i-1].ss); 
		else{
			int a = vv[i].ss, b = vv[i-1].ss;
			merge(a, b);
			tmp += abs(vv[i].ff.ff - vv[i-1].ff.ss) * 2;
		}
	}
	return sum[f(s)] + tmp;
}

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