Submission #810921

#	Time	Username	Problem	Language	Result	Execution time	Memory
810921		WongChun1234	Ancient Books (IOI17_books)	C++14	0 / 100	790 ms	1048576 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4000050;
int n,pt,cmx,st,vis[N],par[N],mx[N],mn[N],rrl[N],dist[5][N],lb,rb;
ll ans=LLONG_MAX,cyc;
queue<int> curr[N];
vector<pair<int,int>> adj[2][N];

void addedge(int u,int v,int w){
	adj[0][u].push_back({v,w});
	adj[1][v].push_back({u,w});
}

void build(int id,int l,int r){
	if (l==r){
		rrl[l]=id;
		return;
	}
	int m=(l+r)/2;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	addedge(id,id*2,0);
	addedge(id,id*2+1,0);
}

void modify(int id,int l,int r,int ql,int qr,int v){
	if (l>qr||r<ql) return;
	if (l>=ql&&r<=qr){
		addedge(v,id,0);
		return;
	}
	int m=(l+r)/2;
	modify(id*2,l,m,ql,qr,v);
	modify(id*2+1,m+1,r,ql,qr,v);
}

void bfs(int s,int id,int sav){
	for (int i=0;i<N;i++) dist[sav][i]=N<<2;
	dist[sav][s]=0; curr[0].push(s);
	for (int i=0;i<N;i++){
		while (curr[i].size()){
			int cnde=curr[i].front();
			curr[i].pop();
			for (auto j:adj[id][cnde]) if (dist[sav][cnde]+j.second<dist[sav][j.first]){
				dist[sav][j.first]=dist[sav][cnde]+j.second;
				curr[dist[sav][j.first]].push(j.first);
			}
		}
	}
}

ll minimum_walk(vector<int> p, int s) {
	n=p.size();
	for (int i=0;i<n;i++){
		if (vis[i]) continue;
		par[i]=i; vis[i]=1; mx[i]=mn[i]=i; cyc+=abs(i-p[i]);
		for (int j=p[i];j!=i;j=p[j]) mx[i]=max(mx[i],j),mn[i]=min(mn[i],j),vis[j]=1,par[j]=i,cyc+=abs(j-p[j]);
	}
	//for (int i=0;i<n;i++) cout<<i<<": "<<par[i]<<" "<<mx[i]<<" "<<sz[i]<<"\n";
	memset(vis,0,sizeof(vis));
	build(1,0,n-1);
	for (int i=1;i<n;i++) addedge(rrl[i],rrl[i-1],1),addedge(rrl[i-1],rrl[i],1);
	for (int i=0;i<n;i++) modify(1,0,n-1,mn[i],mx[i],rrl[i]);
	lb=0,rb=n-1;
	while (p[lb]==lb&&lb<s) lb++;
	while (p[rb]==rb&&rb>s) rb--;
	bfs(rrl[s],0,0);
	bfs(rrl[lb],1,1);
	bfs(rrl[rb],1,2);
	for (int i=0;i<N;i++) ans=min(ans,(ll)dist[0][i]+dist[1][i]+dist[2][i]);
	return cyc+ans*2;
}

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