Submission #53206

#	Time	Username	Problem	Language	Result	Execution time	Memory
53206		WA_TLE	Ancient Books (IOI17_books)	C++14	0 / 100	4 ms	880 KiB

books

#include "books.h"
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}

//void SO(vector<int>& in){sort(in.begin(),in.end());}
long long minimum_walk(std::vector<int> p, int s) {
	llint i,j,n=p.size(),ans=0;
	for(i=0;i<n;i++){ans+=abs(p[i]-i);}
	vector<int>rop(n,-1);
	int ban=0;
	for(i=0;i<n;i++){
		int gen=i;
		if(rop[gen]!=-1){continue;}
		if(p[i]==i){continue;}//元からあってるやつは含めない
		do{
			rop[gen]=ban;
			gen=p[gen];
		}while(gen!=i);
		ban++;
	}
	//うまくマージしてかっこ列にする
	//union-find
	if(rop[s]==-1){
		rop[s]=ban;
		ban++;
	}//sはどうしてもループの中にいたい
	vector<int>hi(ban,mod);
	vector<int>mg(ban);
	cerr<<"de"<<__LINE__<<endl;
	int zenhi=mod,zenmg=mod;
	for(i=0;i<n;i++){
		if(rop[i]==-1){continue;}
		if(zenhi==mod){zenhi=i;}
		zenmg=i;
		if(hi[rop[i]]==mod){hi[rop[i]]=i;}
		mg[rop[i]]=i;
	}
	//各ループの端が把握できた
	vector<int>oya(ban,-1);
	vector<int>uni(ban);
	for(i=0;i<n;i++){uni[i]=i;}
	stack<int>stk;stk.push(-1);
	
	for(i=0;i<n;i++){
		//cerr<<"de"<<__LINE__<<endl;
		if(rop[i]==-1){continue;}
		int ter=rop[i];
		while(uni[ter]!=ter){ter=uni[ter];}
		int gen=rop[i];
		while(uni[gen]!=ter){
			int mto=gen;
			gen=uni[gen];
			uni[mto]=ter;
		}//経路圧縮
		//cerr<<"de"<<__LINE__<<endl;
		if(hi[ter]==i){stk.push(ter);}
		while(-1){
			//マージする
			int ue=stk.top();
			if(ue==ter){break;}
			stk.pop();
			uni[ue]=ter;
			maxeq(mg[ter],mg[ue]);
		}
		if(mg[ter]==i){stk.pop();oya[ter]=stk.top();}
	}
	//経路圧縮を極限まですることでO(1)参照します
	//これ以降マージをしないので..
	for(i=0;i<ban;i++){
		int ter=i;
		while(uni[ter]!=ter){ter=uni[ter];}
		int gen=i;
		while(uni[gen]!=ter){
			int mto=gen;
			gen=uni[gen];
			uni[mto]=ter;
		}//経路圧縮
	}
	int dco=uni[rop[s]];
	while(oya[dco]!=-1){
		int hikyo=0;
		int mgkyo=0;
		//cerr<<"de"<<__LINE__;
		int nobas=hi[dco];
		while(rop[nobas]==-1||uni[rop[nobas]]!=uni[oya[dco]]){
			hikyo+=2;
			nobas--;
			if(rop[nobas]!=-1){mineq(nobas,hi[uni[rop[nobas]]]);}
		}
		//cerr<<"de"<<__LINE__;
		nobas=mg[dco];
		while(rop[nobas]==-1||uni[rop[nobas]]!=uni[oya[dco]]){
			mgkyo+=2;
			nobas++;
			if(rop[nobas]!=-1){maxeq(nobas,mg[uni[rop[nobas]]]);}
		}
		//cerr<<"de"<<__LINE__;
		ans+=min(hikyo,mgkyo);
		dco=uni[oya[dco]];
	}
	int nobas=hi[dco];
	while(nobas!=zenhi){
		ans+=2;
		nobas--;
		if(rop[nobas]!=-1){mineq(nobas,hi[uni[rop[nobas]]]);}
	}
	nobas=mg[dco];
	while(nobas!=zenmg){
		ans+=2;
		nobas++;
		if(rop[nobas]!=-1){maxeq(nobas,mg[uni[rop[nobas]]]);}
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:54:10: warning: unused variable 'j' [-Wunused-variable]
  llint i,j,n=p.size(),ans=0;
          ^

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