Submission #73512

#	Time	Username	Problem	Language	Result	Execution time	Memory
73512		Pajaraja	Ancient Books (IOI17_books)	C++17	50 / 100	301 ms	9468 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define MAXN 1000007
using namespace std;
bool vi[MAXN];
int a[MAXN],mik[MAXN],mak[MAXN],cnt;
long long d[1007][1007];
long long md[MAXN];
long long MST()
{
	for(int i=2;i<=cnt;i++) {vi[i]=false; md[i]=MAXN;}
	md[0]=0;
	long long t=0;
	for(int x=0;x<cnt;x++)
	{
		pair<long long,int> mi=make_pair(MAXN,0);
		for(int i=1;i<=cnt;i++) if(!vi[i]) mi=min(make_pair(md[i],i),mi);
		int u=mi.second;
		t+=mi.first;
		vi[u]=true;
		for(int i=1;i<=cnt;i++) if(!vi[i]) md[i]=min(md[i],d[u][i]);
	}
	return t;
}
long long minimum_walk(std::vector<int> p, int s) 
{
	if(s==0)
	{
		long long sk=0;
		int mx=0;
		for(int i=0;i<p.size();i++) if(!vi[i])
		{
			if(i>mx && p[i]!=i) sk+=2*((long long)i-mx);
			int prev=i;
			while(!vi[i])
			{
				if(p[i]!=i) mx=max(i,mx);
				vi[i]=true;
				i=p[i];
				sk+=abs((long long)i-prev);
				prev=i;
			}
		}
		return sk;
	}
	long long sk=0;
	for(int i=0;i<p.size();i++) if(!vi[i])
	{
		if(p[i]==i) continue;
		int prev=i;
		++cnt;
		mik[cnt]=mak[cnt]=i;
		while(!vi[i])
		{
			a[i]=cnt;
			mik[cnt]=min(mik[cnt],i);
			mak[cnt]=max(mak[cnt],i);
			vi[i]=true;
			i=p[i];
			sk+=abs((long long)i-prev);
			prev=i;
		}
	}
	if(p[s]==s) {a[s]=++cnt; mak[cnt]=mik[cnt]=s;}
	for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
	{
		if(j>=mik[cnt] && j<=mak[cnt]) d[cnt][a[j]]=0;
		else d[cnt][a[j]]=min(d[cnt][a[j]],max((long long)mik[cnt]-j,(long long)j-mak[cnt]));
	}
	return sk+2LL*MST();
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();i++) if(!vi[i])
               ~^~~~~~~~~
books.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<p.size();i++) if(!vi[i])
              ~^~~~~~~~~
books.cpp:65:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
                                      ~^~~~~~~~~

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