Submission #152544

#	Time	Username	Problem	Language	Result	Execution time	Memory
152544		MoNsTeR_CuBe	Ancient Books (IOI17_books)	C++17	0 / 100	2 ms	376 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

#define int long long 
 
vector< int > DSU;
vector< int > Size;

int getParents(int a){
	if(DSU[a] == a)return a;
	else return DSU[a] = getParents(DSU[a]);
}

void Union(int a, int b){
	a = getParents(a);
	b = getParents(b);
	
	if(a == b) return;
	
	if(Size[a] < Size[b]){
		DSU[a] = b;
		Size[b] += Size[a];
	}else{
		DSU[b] = a;
		Size[a] += Size[b];
	}
}

#undef int
long long minimum_walk(vector<int> order, int S) {
	#define int long long 
	int n = order.size();
	DSU.resize(n+1);
	Size.assign(n+1, 1);
	
	for(int i = 0; i <= n; i++){
		DSU[i] = i;
	}
	
	int ans = 0;
	
	for(int i = 0; i < n; i++){
		ans += abs(order[i]-i);
		Union(i, order[i]);
	}
	
	int last = -1;
	
	for(int i = S+1; i < n; i++){
		if(getParents(i) != getParents(i-1)){
			if(last == -1) last = i-1;
			if(Size[getParents(i)] >= 2){
				ans += 2*(i - last);
				last = -1;
			}
		}
	}
	
	return ans;

}

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