Submission #286905

#	Time	Username	Problem	Language	Result	Execution time	Memory
286905		tmwilliamlin168	Ancient Books (IOI17_books)	C++14	100 / 100	1147 ms	209380 KiB

books

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

#define ll long long
#define ar array

const int mxN=1e6;
int n, a, b, who[mxN];
vector<int> adj[mxN], adj2[mxN], st, adj3[mxN], c;
bool vis[mxN];
ar<int, 3> dp[mxN];

void dfs1(int u) {
	vis[u]=1;
	for(int v : adj[u])
		if(!vis[v])
			dfs1(v);
	st.push_back(u);
}

void dfs2(int u, int r) {
	vis[u]=0;
	c.push_back(u);
	who[u]=r;
	for(int v : adj2[u])
		if(vis[v])
			dfs2(v, r);
}

ll minimum_walk(vector<int> p, int s) {
	n=p.size();
	ll ans=0;
	for(; a<s&&p[a]==a; ++a);
	for(b=n-1; b>s&&p[b]==b; --b);
	for(int i=a; i<s; ++i)
		adj[i].push_back(i+1);
	for(int i=b; i>s; --i)
		adj[i].push_back(i-1);
	for(int i=a; i<=b; ++i) {
		ans+=abs(i-p[i]);
		adj[i].push_back(p[i]);
	}
	for(int i=a; i<=b; ++i)
		if(!vis[i])
			dfs1(i);
	for(int i=a; i<=b; ++i)
		for(int j : adj[i])
			adj2[j].push_back(i);
	for(int i=b-a; ~i; --i) {
		if(!vis[st[i]])
			continue;
		dfs2(st[i], st[i]);
		dp[st[i]]={n, n, n};
		if(!vis[a]&&st[i]==who[a])
			dp[st[i]][0]=0;
		if(!vis[b]&&st[i]==who[b])
			dp[st[i]][1]=0;
		for(int u : c)
			for(int v : adj2[u])
				for(int k : {0, 1, 2})
					dp[st[i]][k]=min(dp[who[v]][k]+1, dp[st[i]][k]);
		dp[st[i]][2]=min(dp[st[i]][0]+dp[st[i]][1], dp[st[i]][2]);
		c.clear();
	}
	return ans+2*dp[who[s]][2];
}

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