제출 #993730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993730		zsombor	공장들 (JOI14_factories)	C++17	15 / 100	8061 ms	190656 KiB

factories

#include "factories.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

int n, sz, C;
vector <vector <pair <int, ll>>> g(6e5);
vector <vector <int>> lift(6e5, vector<int>(20, 5e5));
vector <int> dep(6e5, 0);
vector <ll> dis(6e5, 0);

vector <bool> del(6e5, false);
vector <int> par(6e5, -1);
vector <ll> mn(6e5, 1e18);
queue <int> q;

void dfs(int x) {
	for (auto& p : g[x]) {
		ll y = p.first, w = p.second;
		if (lift[x][0] == y) continue;
		lift[y][0] = x;
		dep[y] = dep[x] + 1;
		dis[y] = dis[x] + w;
		dfs(y);
	}
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int j = 19; j >= 0; j--) {
		if (dep[lift[a][j]] >= dep[b]) a = lift[a][j];
	}
	if (a == b) return a;
	for (int j = 19; j >= 0; j--) {
		if (lift[a][j] == lift[b][j]) continue;
		a = lift[a][j];
		b = lift[b][j];
	}
	return lift[a][0];
}

ll dist(int a, int b) {
	int c = lca(a, b);
	return dis[a] + dis[b] - 2 * dis[c];
}

int get_C(int x) {
	if (del[x]) return 0;
	del[x] = true;
	int mx = 0, sum = 1;
	for (auto& p : g[x]) {
		int y = p.first, cur;
		cur = get_C(y);
		mx = max(mx, cur);
		sum += cur;
	}
	mx = max(mx, sz - sum);
	if (mx <= sz / 2) C = x;
	del[x] = false;
	return sum;
}

void cd(int x, int p) {
	if (del[x]) return;
	sz = get_C(x);
	get_C(x);
	int c = C;
	del[c] = true;
	par[c] = p;
	for (auto& p : g[c]) cd(p.first, c);
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		g[A[i]].push_back({ B[i],D[i] });
		g[B[i]].push_back({ A[i],D[i] });
	}
	dfs(0);
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < n; i++) {
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}
	cd(0, -1);
}

void add(int x) {
	int i = x;
	while (i > -1) {
		mn[i] = min(mn[i], dist(x, i));
		q.push(i);
		i = par[i];
	}
}

ll ask(int x) {
	ll i = x, ret = 1e18;
	while (i > -1) {
		ret = min(ret, dist(x, i) + mn[i]);
		i = par[i];
	}
	return ret;
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = 1e18;
	for (int i = 0; i < T; i++) add(Y[i]);
	for (int i = 0; i < S; i++) ans = min(ans, ask(X[i]));
	while (q.size()) { mn[q.front()] = 1e18; q.pop(); }
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67