Submission #797423

#	Time	Username	Problem	Language	Result	Execution time	Memory
797423		firewater	Ancient Books (IOI17_books)	C++14	0 / 100	21 ms	3284 KiB

books

#include "books.h"
#include <cstdio>
#include <vector>
#include <cassert>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 1010
#define mp make_pair
#define fs first
#define sn second
using namespace std;

int n,m,w,x,y,s,ans,to[N],p[N],mx[N],mi[N],fa[N];
pair<int,pair<int,int> >l[N*N];
void dfs(int x)
{
	if(p[x])return;
	p[x]=1;

	mx[w]=max(mx[w],x);
	mi[w]=min(mi[w],x);
	ans+=abs(x-to[x]);
	dfs(to[x]);
	return;
}
int find(int x)
{
	return (fa[x]==x?x:fa[x]=find(fa[x]));
}
long long minimum_walk(std::vector<int> too, int ss) {
	n=too.size();
	for(int i=1;i<=n;++i)
		to[i]=too[i-1]+1;
	s=ss+1;

	w=m=0;
	for(int i=1;i<=n;++i)
		if(!p[i]){
			++w;
			mi[w]=1001000;
			mx[w]=0;
			dfs(i);
		}
	w++;
	mx[w]=s;
	mi[w]=s;
	for(int i=1;i<=w;++i)
		for(int j=i+1;j<=w;++j){
			if(mi[i]<=mx[j]&&mi[j]<=mx[i])l[++m]=mp(0,mp(i,j));
			else l[++m]=mp(min(abs(mi[i]-mx[j]),abs(mi[j]-mx[i]))*2,mp(i,j));
		}
	printf("%d %d\n",w,m);
	sort(l+1,l+1+m);
	for(int i=1;i<=w;++i)
		fa[i]=i;
	for(int i=1;i<=m;++i){
		x=l[i].sn.fs;
		y=l[i].sn.sn;
		x=find(x);
		y=find(y);
		if(x==y)continue;
		ans+=l[i].fs;
		fa[x]=y;
	}
	return ans;
}

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