제출 #515289

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515289		Jomnoi	공장들 (JOI14_factories)	C++17	0 / 100	8087 ms	98804 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define DEBUG 0
using namespace std;

const int MX = 5e5 + 10;
const long long INF = 1e18 + 7;

int sz[MX];
vector <pair <int, int>> adj[MX];
bool visited[MX];
int ancestor[MX];
int depth[MX], parent[MX][21];
long long dist[MX];
long long ans[MX];

void preprocess_lca(int u, int p) {
	for(auto [v, w] : adj[u]) {
		if(v == p) {
			continue;
		}

		depth[v] = depth[u] + 1;
		dist[v] = dist[u] + w;
		parent[v][0] = u;
		preprocess_lca(v, u);
	}
}

int find_size(int u, int p) {
	for(auto [v, w] : adj[u]) {
		if(v == p or visited[v]) {
			continue;
		}

		sz[u] += find_size(v, u);
	}
	return ++sz[u];
}

int find_centroid(int u, int p, int n) {
	for(auto [v, w] : adj[u]) {
		if(v == p or visited[v]) {
			continue;
		}

		if(sz[v] > n / 2) {
			return find_centroid(v, u, n);
		}
	}
	return u;
}

void build_centroid(int u, int p) {
	int c = find_centroid(u, -1, find_size(u, -1));
	ancestor[c] = p;
	visited[c] = true;

	for(auto [v, w] : adj[c]) {
		if(visited[v] == false) {
			build_centroid(v, c);
		}
	}
}

int lca(int u, int v) {
	if(depth[u] < depth[v]) {
		swap(u, v);
	}
	for(int i = 20; i >= 0; i--) {
		if(depth[parent[u][i]] >= depth[v]) {
			u = parent[u][i];
		}
	}
	for(int i = 20; i >= 0; i--) {
		if(parent[u][i] != parent[v][i]) {
			u = parent[u][i];
			v = parent[v][i];
		}
	}
	return (u != v ? parent[u][0] : u);
}

long long get_dist(int u, int v) {
	int l = lca(u, v);
	return dist[u] + dist[v] - 2 * dist[l];
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N - 1; i++) {
		A[i]++, B[i]++;
		adj[A[i]].emplace_back(B[i], D[i]);
		adj[B[i]].emplace_back(A[i], D[i]);
	}

	depth[0] = -1;
	preprocess_lca(1, -1);
	build_centroid(1, -1);

	for(int j = 1; j < 21; j++) {
		for(int i = 1; i <= N; i++) {
			parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
	}
	for(int i = 1; i <= N; i++) {
		ans[i] = INF;
	}
}

void reset(int u) {
	int a = u;
	while(a != -1) {
		ans[a] = INF;
		a = ancestor[a];
	}
}

void update(int u) {
	int a = u;
	while(a != -1) {
		ans[a] = min(ans[a], get_dist(a, u));
		a = ancestor[a];
	}
}

long long query(int u) {
	int a = u;
	long long res = INF;
	while(a != -1) {
		res = min(res, ans[a] + get_dist(a, u));
		a = ancestor[a];
	}
	return res;
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i++) {
		update(X[i] + 1);
	}

	long long res = INF;
	for(int i = 0; i < T; i++) {
		res = min(res, query(Y[i] + 1));
	}

	for(int i = 0; i < S; i++) {
		reset(X[i] + 1);
	}
	return res;
}

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