Submission #797495

#	Time	Username	Problem	Language	Result	Execution time	Memory
797495		firewater	Ancient Books (IOI17_books)	C++14	22 / 100	286 ms	239068 KiB

books

#include "books.h"
#include <cstdio>
#include <vector>
#include<queue>
#include <cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1001000
#define mp make_pair
#define fs first
#define sn second
using namespace std;

ll n,m,w,x,y,s,ans,tot,h[N],b[N],p[N],to[N],mx[N],mi[N],fa[N],fr[N];
priority_queue<pair<ll,ll> >d;
struct rec
{
	int to,nx,l;
}e[N<<3];
void dfs(ll x)
{
	if(fr[x])return;

	fr[x]=w;
	mx[w]=max(mx[w],x);
	mi[w]=min(mi[w],x);
	ans+=abs(x-to[x]);
	dfs(to[x]);
	return;
}
void addl(ll x,ll y,ll z)
{
	e[++tot].to=y;
	e[tot].nx=h[x];
	e[tot].l=z;
	h[x]=tot;
	return;
}
void dij()
{
	memset(p,0,sizeof(p));
	memset(b,127/3,sizeof(b));
	b[w]=0;
	d.push(mp(0,w));
	while(!d.empty()){
		ll x=d.top().sn;
		d.pop();
		if(p[x])continue;
		p[x]=1;
		ans+=b[x];

		for(ll i=h[x];i;i=e[i].nx){
			ll y=e[i].to;
			if(p[y]||e[i].l>b[y])continue;
			b[y]=e[i].l;
			d.push(mp(-b[y],y));
		}
	}
	return;
}
long long minimum_walk(std::vector<int> too, int ss) {
	n=too.size();
	for(ll i=1;i<=n;++i)
		to[i]=too[i-1]+1;
	s=ss+1;

	w=m=0;
	for(ll i=1;i<=n;++i)
		if(!fr[i]&&to[i]!=i){
			++w;
			mi[w]=1001000;
			mx[w]=0;
			dfs(i);
		}
	for(ll i=1;i<=n;++i)
		for(ll j=i+1;j<=n;++j)
			if(fr[i]!=fr[j]&&fr[i]&&fr[j]){
				addl(fr[i],fr[j],abs(j-i)*2);
				addl(fr[j],fr[i],abs(j-i)*2);
			}
				// l[++m]=mp((j-i)*2,mp(fr[i],fr[j]));
	for(ll i=1;i<=n;++i)
		for(ll j=1;j<=w;++j)
			if(fr[i]&&fr[i]!=j&&mi[j]<=i&&i<=mx[j]){
				addl(j,fr[i],0);
			}
				// l[++m]=mp(0,mp(fr[i],j));
	w++;
	for(ll i=1;i<=n;++i)
		if(fr[i]){
			addl(w,fr[i],abs(s-i)*2);
		}
			// l[++m]=mp(abs(s-i)*2,mp(w,fr[i]));
	dij();
	// printf("%d\n",ans);
	// for(ll i=1;i<=m;++i){
	// 	x=l[i].sn.fs;
	// 	y=l[i].sn.sn;
	// 	x=find(x);
	// 	y=find(y);
	// 	if(x==y)continue;
	// 	ans+=l[i].fs;
	// 	fa[x]=y;
	// }
	return ans;
}

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