Submission #609700

#	Time	Username	Problem	Language	Result	Execution time	Memory
609700		dnass	Ancient Books (IOI17_books)	C++17	100 / 100	390 ms	124528 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define INF 1000000000000000000LL
#define ff first
#define ss second

lld n;
lld comps;
lld cyc[1000100];
vector<vector<lld>> cycles;
pair<pair<lld,lld>,pair<lld,lld>> reach[1000100];
lld lfinal, rfinal;
lld par[1000100], sz[1000100];

lld find(lld x){
	if(x==par[x]) return x;
	return par[x] = find(par[x]);
}

void uni(lld a, lld b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	if(sz[a]>sz[b]) swap(a,b);
	sz[b] += sz[a];
	par[a] = b;
}

bool cmp(lld comp1, lld comp2){
	return reach[comp1].ss.ff<reach[comp2].ss.ff;
}

void debug(){
	for(lld i=0;i<n;i++) cout << find(cyc[i]) << " \n"[i==n-1];
	for(lld i=0;i<comps;i++)
		if((lld)cycles[i].size()>1) cout << i << ": " << reach[i].ff.ff << " " << reach[i].ff.ss << " " << reach[i].ss.ff << " " << reach[i].ss.ss << "\n";
}

lld minimum_walk(vector<int> p, int s){
	n = (lld) p.size();
	lld ans = 0;
	for(lld i=0;i<n;i++) ans+=abs(p[i]-i);
	for(lld i=0;i<n;i++){
		par[i] = i;
		sz[i] = 1;
	}
	vector<bool> vis(n, false);
	comps = 0;
	lfinal = s, rfinal = s;
	for(lld i=0;i<n;i++){
		if(!vis[i]){
			vector<lld> tmp;
			lld x = i;
			while(true){
				if(vis[x]) break;
				tmp.push_back(x);
				vis[x] = true;
				cyc[x] = comps;
				x = p[x];
			}
			sort(tmp.begin(), tmp.end());
			cycles.push_back(tmp);
			if((int)tmp.size()>1){
				if(tmp.front()>=s) reach[comps] = {{tmp.front(),-1},{tmp.front(),tmp.back()}};
				else if(tmp.back()<=s) reach[comps] = {{tmp.front(),tmp.back()},{INF,tmp.back()}};
				else{
					auto it = lower_bound(tmp.begin(), tmp.end(), s);
					reach[comps] = {{tmp.front(),*prev(it)},{*it,tmp.back()}};
				}
				lfinal = min(lfinal, reach[comps].ff.ff);
				rfinal = max(rfinal, reach[comps].ss.ss);
			}else{
				reach[comps] = {{tmp[0],tmp[0]},{tmp[0],tmp[0]}};
			}
			comps++;
		}
	}
	lld cur_comp = find(cyc[s]);
	lld lblock = s, rblock = s;
	lld lblocknew = reach[cur_comp].ff.ff, rblocknew = reach[cur_comp].ss.ss;
	while(lblocknew!=lblock||rblocknew!=rblock){
		lld lblocknewnew, rblocknewnew;
		for(lld i=lblocknew;i<=lblock;i++){
			if((lld)cycles[find(cyc[i])].size()==1) continue;
			reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[find(cyc[i])].ff.ff);
			reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[find(cyc[i])].ff.ss);
			reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[find(cyc[i])].ss.ff);
			reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[find(cyc[i])].ss.ss);
			lblocknewnew = reach[cur_comp].ff.ff;
			rblocknewnew = reach[cur_comp].ss.ss;
			uni(cyc[i], cur_comp);
			cyc[i] = cur_comp;
		}
		for(lld i=rblock;i<=rblocknew;i++){
			if((lld)cycles[find(cyc[i])].size()==1) continue;
			reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[find(cyc[i])].ff.ff);
			reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[find(cyc[i])].ff.ss);
			reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[find(cyc[i])].ss.ff);
			reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[find(cyc[i])].ss.ss);
			lblocknewnew = reach[cur_comp].ff.ff;
			rblocknewnew = reach[cur_comp].ss.ss;
			uni(cyc[i], cur_comp);
			cyc[i] = cur_comp;
		}
		lblock = lblocknew; rblock = rblocknew;
		lblocknew = lblocknewnew; rblocknew = rblocknewnew;
	}
	lld l = INF;
	for(lld i=lblock-1;i>=lfinal;i--){
		if((lld)cycles[find(cyc[i])].size()==1) continue;
		if(i<l){
			cur_comp = find(cyc[i]);
			l = reach[cur_comp].ff.ff;
		}else{
			reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[find(cyc[i])].ff.ff);
			reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[find(cyc[i])].ff.ss);
			reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[find(cyc[i])].ss.ff);
			reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[find(cyc[i])].ss.ss);
			l = reach[cur_comp].ff.ff;
			uni(cyc[i], cur_comp);
			cyc[i] = cur_comp;
		}
	}
	lld r = -1;
	for(lld i=rblock+1;i<=rfinal;i++){
		if((lld)cycles[find(cyc[i])].size()==1) continue;
		if(i>r){
			cur_comp = find(cyc[i]);
			r = reach[cur_comp].ss.ss;
		}else{
			reach[cur_comp].ff.ff = min(reach[cur_comp].ff.ff, reach[find(cyc[i])].ff.ff);
			reach[cur_comp].ff.ss = max(reach[cur_comp].ff.ss, reach[find(cyc[i])].ff.ss);
			reach[cur_comp].ss.ff = min(reach[cur_comp].ss.ff, reach[find(cyc[i])].ss.ff);
			reach[cur_comp].ss.ss = max(reach[cur_comp].ss.ss, reach[find(cyc[i])].ss.ss);
			r = reach[cur_comp].ss.ss;
			uni(cyc[i], cur_comp);
			cyc[i] = cur_comp;
		}
	}
	//debug();
	set<lld> brid;
	for(lld i=0;i<n;i++){
		if((lld)cycles[find(cyc[i])].size()==1) continue;
		if(reach[find(cyc[i])].ff.ff<s&&reach[find(cyc[i])].ss.ss>s) brid.insert(find(cyc[i]));
	}
	vector<lld> bridges;
	for(lld xxx:brid) bridges.push_back(xxx);
	sort(bridges.begin(), bridges.end(), cmp);
	for(lld i=1;i<(lld)bridges.size();i++){
		if(reach[bridges[i-1]].ss.ss>reach[bridges[i]].ss.ff||reach[bridges[i-1]].ff.ff<reach[bridges[i]].ff.ss){
			reach[find(bridges[i-1])].ff.ff = min(reach[find(bridges[i-1])].ff.ff, reach[find(bridges[i])].ff.ff);
			reach[find(bridges[i-1])].ff.ss = max(reach[find(bridges[i-1])].ff.ss, reach[find(bridges[i])].ff.ss);
			reach[find(bridges[i-1])].ss.ff = min(reach[find(bridges[i-1])].ss.ff, reach[find(bridges[i])].ss.ff);
			reach[find(bridges[i-1])].ss.ss = max(reach[find(bridges[i-1])].ss.ss, reach[find(bridges[i])].ss.ss);
			reach[find(bridges[i])] = reach[find(bridges[i-1])];
			uni(bridges[i-1], bridges[i]);
		}
	}
	l = lblock, r = rblock;
	while(l>lfinal||r<rfinal){
		lld i, j;
		lld lpath = (l-1<lfinal?INF:0), rpath = (r+1>rfinal?INF:0);
		bool found_bridge = false;
		for(i=l-1;i>=lfinal;i--){
			if(reach[find(cyc[i])].ff.ff<s&&reach[find(cyc[i])].ss.ss>s){
				lpath+=2;
				found_bridge = true;
				break;
			}
			if(find(cyc[i])!=find(cyc[i+1])) lpath+=2;
			i = reach[find(cyc[i])].ff.ff;
			if(i==lfinal) break;
		}
		for(j=r+1;j<=rfinal;j++){
			if(reach[find(cyc[j])].ff.ff<s&&reach[find(cyc[j])].ss.ss>s){
				found_bridge = true;
				rpath+=2;
				break;
			}
			if(find(cyc[j])!=find(cyc[j-1])) rpath+=2;
			j = reach[find(cyc[j])].ss.ss;
			if(j==rfinal) break;
		}
		if(found_bridge) ans += min(lpath, rpath);
		else ans += (lpath==INF?0:lpath)+(rpath==INF?0:rpath);
		if(l-1>=lfinal)l = reach[find(cyc[i])].ff.ff;
		if(r+1<=rfinal)r = reach[find(cyc[j])].ss.ss;
		//printf("------------\n%lld %lld\n--------------\n",l,r);
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'lld minimum_walk(std::vector<int>, int)':
books.cpp:83:36: warning: 'rblocknewnew' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |  while(lblocknew!=lblock||rblocknew!=rblock){
      |                           ~~~~~~~~~^~~~~~~~
books.cpp:83:17: warning: 'lblocknewnew' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |  while(lblocknew!=lblock||rblocknew!=rblock){
      |        ~~~~~~~~~^~~~~~~~

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