Submission #294079

#	Time	Username	Problem	Language	Result	Execution time	Memory
294079		Pajaraja	Ancient Books (IOI17_books)	C++17	22 / 100	708 ms	65172 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) 
{
	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:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<p.size();i++) if(!vi[i])
      |              ~^~~~~~~~~
books.cpp:47:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  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: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30