Submission #390551

#	Time	Username	Problem	Language	Result	Execution time	Memory
390551		Keshi	Ancient Books (IOI17_books)	C++17	50 / 100	336 ms	161876 KiB

books

//In the name of God
#include <bits/stdc++.h>
#include "books.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 1e6 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll a[maxn], t, tt, c[maxn], par[maxn];
ll mn[maxn], mx[maxn], mnp[maxn], mxp[maxn];
bool vis[maxn];
vector<ll> vec, g[maxn], gp[maxn], gg[maxn];
vector<pll> v2;

void dfs(ll v){
	vis[v] = 1;
	for(ll u : g[v]){
		if(!vis[u]) dfs(u);
	}
	vec.pb(v);
}
void sfd(ll v){
	vis[v] = 1;
	c[v] = tt;
	mnp[tt] = min(mnp[tt], mn[v]);
	mxp[tt] = max(mxp[tt], mx[v]);
	for(ll u : gp[v]){
		if(!vis[u]) sfd(u);
	}
}

ll solve(ll v, ll s){
	ll x = 0;
	ll ans = 0;
	ll i = 0;
	for(ll u : gg[v]){
		if(mnp[u] <= s && s <= mxp[u]) x = i;
		ans += solve(u, s);
		i++;
	}
	if(mnp[v] == -1){
		return ans + Sz(gg[v]) - 1;
	}
	ans += max(0ll, min(x, Sz(gg[v]) - x - 1));
	return ans;
}

long long minimum_walk(vector<int> p, int s){
	ll n = Sz(p);
	ll l = 0;
	while(l < n && p[l] == l) l++;
	ll r = n;
	while(r && p[r - 1] == r - 1) r--;
	l = min(l, (ll)s);
	r = max(r, s + 1ll);
	mn[0] = -1;
	mx[0] = n + 1;
	t++;
	for(ll i = l; i < r; i++){
		if(p[i] > i){
			a[i]++;
			a[p[i]]--;
		}
		if(!vis[i]){
			ll v = i;
			mn[t] = inf;
			mx[t] = -inf;
			do{
				vis[v] = 1;
				mx[t] = max(mx[t], v);
				mn[t] = min(mn[t], v);
				v = p[v];
			}while(v != i);
			t++;
		}
	}
	ll ans = 0;
	for(ll i = 1; i < n; i++){
		ans += a[i - 1];
		a[i] += a[i - 1];
	}
	for(ll i = 0; i < s; i++){
		g[c[i]].pb(c[i + 1]);
		gp[c[i + 1]].pb(c[i]);
	}
	for(ll i = s; i + 1 < n; i++){
		g[c[i + 1]].pb(c[i]);
		gp[c[i]].pb(c[i + 1]);
	}
	//  SCC
	fill(vis, vis + t, 0);
	for(ll i = 0; i < t; i++){
		if(!vis[i]) dfs(i);
	}
	reverse(all(vec));
	fill(vis, vis + t, 0);
	for(ll i = 0; i < t; i++){
		if(!vis[vec[i]]){
			mnp[tt] = inf;
			mxp[tt] = -inf;
			sfd(vec[i]);
			tt++;
		}
	}
	vec.clear();
	ll root = -1;
	for(ll i = 0; i < tt; i++){
		if(mnp[i] == -1) root = i;
		v2.pb(Mp(mnp[i], i));
	}
	sort(all(v2));
	for(pll i : v2){
		if(vec.empty()){
			vec.pb(i.S);
			continue;
		}
		while(mxp[vec.back()] < i.F) vec.pop_back();
		gg[vec.back()].pb(i.S);
		vec.pb(i.S);
	}
	ans += solve(root, s);

	return ans * 2;
}

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