Submission #156524

#	Time	Username	Problem	Language	Result	Execution time	Memory
156524		Saboon	공장들 (JOI14_factories)	C++14	15 / 100	8057 ms	117640 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;

int sz[maxn], cpar[maxn], h[maxn], par[maxn][21];
ll dis[maxn], dp[maxn];
bool mark[maxn];
vector<pair<int, int> > t[maxn];

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
	for (int i = 19; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = 19; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];
	return par[v][0];
}

ll distance(int v, int u){
	return dis[v] + dis[u] - 2ll * dis[lca(v, u)];
}

int dfs_sz(int v, int p = -1){
	sz[v] = 1;
	for (auto edge : t[v]){
		int u = edge.first;
		if (u != p and mark[u] == false)
			sz[v] += dfs_sz(u, v);
	}
	return sz[v];
}

void centroid_decomposition(int v, int centpar = -1){
	dfs_sz(v);
	int parent = -1, Mx = sz[v];
	bool flag = 1;
	while (flag){
		flag = 0;
		for (auto edge : t[v]){
			int u = edge.first;
			if (u != parent and mark[u] == false and sz[u] > Mx / 2){
				parent = v;
				v = u;
				flag = 1;
				break;
			}
		}
	}
	cpar[v] = centpar;
	mark[v] = true;
	for (auto u : t[v])
		if (mark[u.first] == false)
			centroid_decomposition(u.first, v);
}

void dfs(int v, int p = -1){
	par[v][0] = p;
	for (int i = 1; par[v][i - 1] != -1 and i <= 19; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto edge : t[v]){
		int u = edge.first, w = edge.second;
		if (u != p){
			h[u] = h[v] + 1;
			dis[u] = dis[v] + w;
			dfs(u, v);
		}
	}
}

void Init(int N, int A[], int B[], int D[]){
	for (int i = 0; i < N - 1; i++){
		int v = A[i], u = B[i], w = D[i];
		t[v].push_back({u, w});
		t[u].push_back({v, w});
	}
	memset(par, -1, sizeof par);
	dfs(0);
	centroid_decomposition(0);
	memset(dp, 63, sizeof dp);
}

long long Query(int S, int X[], int T, int Y[]){
	for (int i = 0; i < S; i++){
		int v = X[i];
		while (v != -1){
			dp[v] = min(dp[v], distance(v, X[i]));
			v = cpar[v];
		}
	}
	ll answer = 1e18;
	for (int i = 0; i < T; i++){
		int v = Y[i];
		while (v != -1){
			answer = min(answer, dp[v] + distance(v, Y[i]));
			v = cpar[v];
		}
	}
	for (int i = 0; i < S; i++){
		int v = X[i];
		while (v != -1){
			dp[v] = 1e18;
			v = cpar[v];
		}
	}
	return answer;
}

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