제출 #288140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288140		user202729	고대 책들 (IOI17_books)	C++17	0 / 100	8 ms	2040 KiB

books

// moreflags=grader.cpp
// 11
// ???
#include "books.h"
#include<algorithm>
#include<numeric>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>


long long minimum_walk(std::vector<int> p, int s) {
	// assert(std::is_permutation(begin(p), end(p)));
	assert(s>=0); assert(s<(int)p.size());
	if(p.size()>1000) return -1;

	int64_t result{};
	for(int index=0; index<(int)p.size(); ++index){
		if(index<p[index]){
			result+=p[index]-index;
		}
	}

	struct Dsu{
		std::vector<int> data;
		void reset(int number){data.assign(number, -1);}
		int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
		bool join(int first, int sec){
			first=root(first); sec=root(sec);
			if(first==sec) return false;
			data[first]=sec;
			return true;
		}
	};
	struct Edge{int first, sec, value;
		bool operator<(Edge other) const{return value<other.value;}
	};
	std::vector<Edge> edges;
	for(int first=0; first<(int)p.size(); ++first) if(first==s or p[first]!=first)
		for(int sec=0; sec<first; ++sec) if(sec==s or p[sec]!=sec){
			auto const [p1, p2]=std::minmax({
				std::minmax({first, p[first]}),
					std::minmax({sec, p[sec]})
			});
			auto const [a, b]=p1; auto const [c, d]=p2;
			edges.push_back({first, sec,
				b<=c ? c-b:
					d<=b ? std::min(b-d, c-a): 0
			});
		}

	std::sort(begin(edges), end(edges));
	Dsu dsu; dsu.reset((int)p.size());
	for(auto [first, sec, value]: edges)
		if(dsu.join(first, sec)) result+=value;

	return result*2;
}

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