oj.uz

답안 #810921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
810921 2023-08-06T17:30:28 Z WongChun1234 고대 책들 (IOI17_books) C++14
0 / 100
 790 ms 1048576 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 790 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 790 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 790 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 605 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 790 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -