Submission #1049607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049607		pcc	Ancient Books (IOI17_books)	C++17	42 / 100	2025 ms	311120 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
const int mxn = 1e6+10;
const int LEN = mxn*20;
int N;

int nid[LEN],to[LEN],wei[LEN],head[LEN];
int d1[LEN],d2[LEN];
ll ans = 0;
bitset<LEN> vis;
int ecnt,vcnt;
int seg[mxn*4];

void add_edge(int a,int b,int w){
	//cerr<<"ADD_EDGE: "<<a<<' '<<b<<' '<<w<<endl;
	ecnt++;
	nid[ecnt] = head[a];
	head[a] = ecnt;
	to[ecnt] = b;
	wei[ecnt] = w;
	return;
}

void build(int now,int l,int r){
	if(l == r){
		seg[now] = l;
		return;
	}
	seg[now] = vcnt++;
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	add_edge(seg[now*2+1],seg[now],0);
	add_edge(seg[now*2+2],seg[now],0);
	//cerr<<l<<' '<<r<<"::"<<seg[now]<<":"<<seg[now*2+1]<<' '<<seg[now*2+2]<<endl;
	return;
}

void add(int now,int l,int r,int s,int e,int p){
	if(l>=s&&e>=r){
		//cerr<<l<<' '<<r<<":"<<p<<endl;
		add_edge(seg[now],p,0);
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)add(now*2+1,l,mid,s,e,p);
	if(mid<e)add(now*2+2,mid+1,r,s,e,p);
	return;
}

priority_queue<pii,vector<pii>,greater<pii>> pq;
void DIJKSTRA(int dist[]){
	vis.reset();
	for(int i = 0;i<vcnt;i++)pq.push(pii(dist[i],i));
	while(!pq.empty()){
		auto [d,now] = pq.top();
		pq.pop();
		if(vis[now])continue;
		vis[now] = true;
		for(int eid = head[now];eid;eid = nid[eid]){
			int nxt = to[eid],w = wei[eid];
			if(dist[nxt]>dist[now]+w){
				dist[nxt] = dist[now]+w;
				pq.push(pii(dist[nxt],nxt));
			}
		}
	}
	return;
}

long long minimum_walk(std::vector<int> p, int s) {
	N = p.size();
	vcnt = N;
	for(int i = 0;i+1<N;i++){
		add_edge(i,i+1,1);
		add_edge(i+1,i,1);
	}
	build(0,0,N-1);
	for(int i = 0;i<p.size();i++){
		ans += abs(i-p[i]);
		if(vis[i])continue;
		int now = i;
		int lp = i,rp = i;
		do{
			lp = min(lp,now);
			rp = max(rp,now);
			vis[now] = true;
			now = p[now];
		}while(now != i);
		int tar = vcnt++;
		add(0,0,N-1,lp,rp,tar);
		do{
			add_edge(tar,now,0);
			now = p[now];
		}while(now != i);
	}
	fill(d1,d1+LEN,LEN);
	fill(d2,d2+LEN,LEN);
	int tl = s,tr = s;
	for(int i = 0;i<N;i++){
		if(p[i] != i)tl = min(tl,i),tr = max(tr,i);
	}
	//cerr<<tl<<','<<tr<<endl;
	d1[tl] = d2[tr] = 0;
	DIJKSTRA(d1);
	DIJKSTRA(d2);
	//for(int i = 0;i<vcnt;i++)cerr<<d1[i]<<' ';cerr<<endl;
	//for(int i = 0;i<vcnt;i++)cerr<<d2[i]<<' ';cerr<<endl;
	for(int i = 0;i<vcnt;i++)d1[i] += d2[i];
	DIJKSTRA(d1);
	//for(int i = 0;i<vcnt;i++)cerr<<d1[i]<<' ';cerr<<endl;
	return ans+d1[s]*2;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:83:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0;i<p.size();i++){
      |                ~^~~~~~~~~

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