Submission #601050

#	Time	Username	Problem	Language	Result	Execution time	Memory
601050		DanShaders	Ancient Books (IOI17_books)	C++17	22 / 100	1622 ms	1048576 KiB

books

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

#define x first
#define y second
#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
using ll = long long;
using ld = long double;

const int N = 1e6 + 10;

int cc[N], cnt[N];
vector<tuple<int, int, int>> edges;

struct DSU {
	int rank[N], parent[N];

	DSU() {
		iota(all(parent), 0);
	}

	int get(int u) {
		if (u == parent[u]) {
			return u;
		}
		return parent[u] = get(parent[u]);
	}

	bool merge(int a, int b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return false;
		}
		if (rank[a] == rank[b]) {
			++rank[a];
		}
		if (rank[a] < rank[b]) {
			swap(a, b);
		}
		parent[b] = a;
		return true;
	}
} dsu;

ll minimum_walk(vector<int> p, int s) {
	int n = sz(p), m = 0;
	ll ans = 0;
	fill(all(cc), -1);
	for (int i = 0; i < n; ++i) {
		ans += abs(p[i] - i);
		if (cc[i] == -1) {
			int j = i;
			while (cc[j] == -1) {
				cc[j] = m;
				cnt[m]++;
				j = p[j];
			}
			++m;
		}
	}
	// cout << ans << endl;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (cc[i] != cc[j]) {
				edges.push_back({abs(i - j), cc[i], cc[j]});
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = min(p[i], i); j < max(p[i], i); ++j) {
			if (cc[i] != cc[j]) {
				edges.push_back({0, cc[i], cc[j]});
			}
		}
	}
	sort(all(edges));
	for (auto [w, u, v] : edges) {
		if (cnt[u] == 1 && u != cc[s]) {
			continue;
		}
		if (cnt[v] == 1 && v != cc[s]) {
			continue;
		}
		if (dsu.merge(u, v)) {
			ans += 2 * w;
		}
	}
	return ans;
}

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