Submission #137600

#	Time	Username	Problem	Language	Result	Execution time	Memory
137600		Mahdi_Jfri	Ancient Books (IOI17_books)	C++14	0 / 100	5 ms	4216 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();

	for(int i = 0; i < n; i++)
		res += abs(p[i] - i) , merge(i , p[i]);

	for(int i = 0; i + 1 < n; i++)
		res += 2 * (int)merge(i , i + 1);
	return res;
}

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