제출 #1147732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147732		gyg	고대 책들 (IOI17_books)	C++20	50 / 100	288 ms	114552 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed 
#define int long long
#define arr array
#define vec vector 
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e6 + 5, INF = 1e18;

int n, st;
arr<int, N> out;

arr<bool, N> vs;
int nm;
arr<vec<int>, N> cyc;
arr<int, N> lf, rg;
void dfs(int u) {
	vs[u] = true;
	cyc[nm].push_back(u), lf[nm] = min(lf[nm], u), rg[nm] = max(rg[nm], u); 
	if (vs[out[u]]) return;
	dfs(out[u]);
}
arr<pii, N> frm;
int cyc_cmp() {
	for (int u = 0; u < n; u++) {
		if (vs[u]) continue;
		if (out[u] == u && u != 0) continue;
		nm++, lf[nm] = INF, rg[nm] = -1;
		dfs(u);
	}
	
	int ans = 0;
	for (int i = 1; i <= nm; i++) {
		for (int j = 0; j < cyc[i].size(); j++) {
			int k = (j + 1) % cyc[i].size();
			ans += abs(cyc[i][j] - cyc[i][k]);
		}
	}

	for (int u = 0; u < n; u++) frm[u] = {-1, -1};
	for (int i = 1; i <= nm; i++)
		frm[lf[i]] = {0, i}, frm[rg[i]] = {1, i};

	// for (int i = 1; i <= nm; i++) {
	// 	cout << i << ": " << mn[i] << " " << mx[i] << endl;
	// 	for (int u : cyc[i]) cout << u << " ";
	// 	cout << endl;
	// }
	return ans;
}

vec<vec<int>> edg;
void edg_cmp() {
	set<int> actv;
	for (int u = 0; u < n; u++) {
		if (frm[u].fir == 0) {
			if (actv.size()) edg.push_back({0, frm[u].sec, *actv.begin()});
			actv.insert(frm[u].sec);
		} else if (frm[u].fir == 1) {
			actv.erase(frm[u].sec);
		}
	}

	pii lst = {-1, -1};
	for (int u = 0; u < n; u++) {
		if (frm[u].fir == 0) {
			if (lst.fir != -1) edg.push_back({2 * (u - lst.fir), frm[u].sec, lst.sec});
		} else if (frm[u].fir == 1) {
			lst = {u, frm[u].sec};
		}
	}

	lst = {-1, -1};
	for (int u = n - 1; u >= 0; u--) {
		if (frm[u].fir != 0) continue;
		if (lst.fir != -1) edg.push_back({2 * (lst.fir - u), frm[u].sec, lst.sec});
		lst = {u, frm[u].sec};
	}
	sort(edg.begin(), edg.end());
}

struct Dsj {
	arr<int, N> prnt;
	void intl() {
		for (int u = 1; u <= nm; u++) prnt[u] = u;
	}
	int pr(int u) {
		return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
	}
	bool mrg(int u, int v) {
		u = pr(u), v = pr(v);
		if (u == v) return false;
		prnt[v] = u;
		return true;
	}
} dsj;
int dsj_cmp() {
	dsj.intl();
	int ans = 0;
	for (vec<int> x : edg) {
		int cst = x[0], u = x[1], v = x[2];
		if (!dsj.mrg(u, v)) continue;
		ans += cst;
	}
	return ans;
}

int minimum_walk(vec<sig> _out, sig _st) {
	n = _out.size(), st = _st;
	for (int u = 0; u < n; u++) out[u] = _out[u];

	int ans = cyc_cmp();
	edg_cmp();
	ans += dsj_cmp();
	
	return ans;
}

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