Submission #782502

#	Time	Username	Problem	Language	Result	Execution time	Memory
782502		GusterGoose27	Ancient Books (IOI17_books)	C++17	0 / 100	35 ms	48112 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+5;

typedef long long ll;
typedef pair<int, int> pii;
bool vis[MAXN];
int uf[MAXN];
vector<int> cont[MAXN];
// pii range[MAXN];
// vector<int> in_comp[MAXN];
int par[MAXN];
int dist[MAXN];

int n;

int _abs(int v) {
	return v < 0 ? -v : v;
}

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

void merge(int i, int j) {
	i = find(i);
	j = find(j);
	// if (i == j) return;
	assert(i != j);
	if (cont[i].size() < cont[j].size()) swap(i, j);
	for (int v: cont[j]) {
		cont[i].push_back(v);
		uf[v] = i;
	}
	cont[j].clear();
	uf[j] = i;
	// range[i].first = min(range[i].first, range[j].first);
	// range[i].second = max(range[i].second, range[j].second);
}

void upd(int cur, queue<int> &q) {
	int cdist = 1+dist[find(cur)];
	if (cur && dist[find(cur-1)] > cdist) {
		assert(dist[find(cur-1)] == MAXN);
		dist[find(cur-1)] = cdist;
		q.push(find(cur-1));
	}
	if (cur < n-1 && dist[find(cur+1)] > cdist) {
		assert(dist[find(cur+1)] == MAXN);
		dist[find(cur+1)] = cdist;
		q.push(find(cur+1));
	}
}

ll minimum_walk(vector<int> p, int s) {
	ll ans = 0;
	n = p.size();
	for (int i = 0; i < n; i++) ans += _abs(p[i]-i);
	if (ans == 0) return 0;
	vector<pii> intervals;
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int cur = i;
		int l = i, r = i;
		do {
			l = min(l, cur);
			r = max(r, cur);
			uf[cur] = i;
			cont[i].push_back(cur);
			vis[cur] = 1;
			cur = p[cur];
		} while (cur != i);
		if (l == r && i == s) intervals.push_back(pii(l, r));
		sort(cont[i].begin(), cont[i].end());
		if (r > l) {
			for (int j = 0; j < cont[i].size()-1; j++) intervals.push_back(pii(cont[i][j], cont[i][j+1]));
		}
		// range[i] = pii(l, r);
	}
	sort(intervals.begin(), intervals.end()); // they are probably already sorted
	fill(dist, dist+n, MAXN);
	int curr = intervals[0].second;
	vector<int> stck;
	for (int i = 0; i < intervals.size(); i++) {
		while (!stck.empty() && stck.back() < intervals[i].first) {
			int v = stck.back(); stck.pop_back();
			if (stck.empty()) dist[find(v)] = 0;
			// else par[find(v)] = find(stck.back());
		}
		while (!stck.empty() && stck.back() <= intervals[i].second) {
			int v = stck.back(); stck.pop_back();
			merge(v, intervals[i].second);
		}
		stck.push_back(intervals[i].second);
		// assert(curr != intervals[i].first);
		if (curr > intervals[i].first) {
			curr = max(curr, intervals[i].second);
			continue;
		}
		ans += 2*(intervals[i].first-curr);
		curr = intervals[i].second;
	}
	// for (int i = 1; i < stck.size(); i++) par[find(stck[i])] = find(stck[i-1]);
	dist[find(stck[0])] = 0;
	queue<int> q;
	for (int i = 0; i < n; i++) {
		if (dist[i] == 0) dist[find(i)] = 0;
	}
	for (int i = 0; i < n; i++) {
		if (i == find(i) && dist[i] == 0) q.push(i);
	}
	while (!q.empty()) {
		int v = q.front(); q.pop();
		for (int e: cont[v]) upd(e, q);
	}
	// return 0;
	// int dist = 0;
	// s = find(s);
	// while (par[s] != -1) {
	// 	int nxt = find(par[s]);
	// 	dist += min(range[nxt].second-range[s].second, range[s].first-range[nxt].first);
	// 	s = nxt;
	// }
	return ans+2*dist[find(s)];
}

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for (int j = 0; j < cont[i].size()-1; j++) intervals.push_back(pii(cont[i][j], cont[i][j+1]));
      |                    ~~^~~~~~~~~~~~~~~~~~
books.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < intervals.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~~

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