Submission #137607

#	Time	Username	Problem	Language	Result	Execution time	Memory
137607		Mahdi_Jfri	Ancient Books (IOI17_books)	C++14	0 / 100	6 ms	4220 KiB

books

#include "books.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;

int par[maxn];

int root(int v)
{
	return par[v] < 0? v : par[v] = root(par[v]);
}

bool merge(int v , int u)
{
	v = root(v) , u = root(u);
	if(v == u)
		return 0;

	par[v] = u;
	return 1;
}

long long minimum_walk(vector<int> p, int s)
{
	memset(par , -1 , sizeof par);
	ll res = 0;
	int n = p.size();

	vector<int> val;
	for(int i = 0; i < n; i++)
	{
		res += abs(p[i] - i) , merge(i , p[i]);
		if(p[i] != i || i == s)
			val.pb(i);
	}

	int m = val.size();
	vector<pair<int , pair<int , int> > > tmp;
	for(int i = 0; i + 1 < m; i++)
		tmp.pb({val[i + 1] - val[i] , {val[i] , val[i + 1]}});
	sort(tmp.begin() , tmp.end());

	for(auto x : tmp)
	{
		int a = x.second.first , b = x.second.second;
		if(merge(a , b))
			res += 2 * x.first;
	}
	return res;
}

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