Submission #73519

#	Time	Username	Problem	Language	Result	Execution time	Memory
73519		Pajaraja	Ancient Books (IOI17_books)	C++17	50 / 100	307 ms	9544 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(int s)
{
	for(int i=1;i<=cnt;i++) {vi[i]=false; md[i]=MAXN;}
	md[s]=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<=cnt;j++) d[i][j]=MAXN;
	for(int i=1;i<=cnt;i++) for(int j=0;j<p.size();j++)
	{
		if(j>=mik[i] && j<=mak[i]) d[i][a[j]]=0;
		else d[i][a[j]]=min(d[i][a[j]],max((long long)mik[i]-j,(long long)j-mak[i]));
	}
	return sk+2LL*MST(a[s]);
}

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:66: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