Submission #1147729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147729		gyg	고대 책들 (IOI17_books)	C++20	22 / 100	964 ms	1114112 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 
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]);
}

int cyc_cmp() {
	nm = 1, cyc[1] = {0}, lf[1] = rg[1] = 0;
	for (int u = 0; u < n; u++) {
		if (vs[u]) continue;
		if (out[u] == u) 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 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() {
	for (int i = 1; i <= nm; i++) {
		for (int j = 1; j <= nm; j++) {
			if (i == j) continue;
			int dst = 0;
			if (lf[j] > rg[i]) dst = 2 * (lf[j] - rg[i]);
			if (lf[j] < lf[i]) dst = 2 * (lf[i] - lf[j]);
			edg.push_back({dst, i, j});
		}
	}
	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: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30