Submission #156529

#	Time	Username	Problem	Language	Result	Execution time	Memory
156529		Saboon	Factories (JOI14_factories)	C++14	100 / 100	6062 ms	183556 KiB

factories

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

int st[maxn], LOG[2 * maxn], a[2 * maxn], sz[maxn], cpar[maxn], h[maxn], RMQ[22][2 * maxn];
int cnt = 0;
ll dis[maxn], dp[maxn];
bool mark[maxn];
vector<pair<int, int> > t[maxn];

int lca(int v, int u){
	if (v == u)
		return v;
	if (st[v] > st[u])
		swap(v, u);
	int len = st[u] - st[v] + 1;
	int lg = LOG[len];
	int me = RMQ[lg][st[v]], oth = RMQ[lg][st[v] + (len - (1 << lg))];
	if (h[me] < h[oth])
		return me;
	return oth;
}

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){
	int Max = dfs_sz(v), parent = -1;
	while (true){
		bool found = 0;
		for (auto edge : t[v]){
			int u = edge.first;
			if (u != parent and mark[u] == false and sz[u] > Max / 2){
				parent = v;
				v = u;
				found = 1;
				break;
			}
		}
		if (!found)
			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 par = -1){
	st[v] = cnt;
	a[cnt ++] = v;
	for (auto edge : t[v]){
		int u = edge.first, w = edge.second;
		if (u != par){
			h[u] = h[v] + 1;
			dis[u] = dis[v] + w;
			dfs(u, v);
			a[cnt ++] = 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});
	}
	dfs(0);
	for (int i = 0; i < cnt; i++)
		RMQ[0][i] = a[i];
	for (int i = 1; i <= 20; i++){
		for (int j = 0; j + (1 << i) <= cnt; j++){
			int me = RMQ[i - 1][j], oth = RMQ[i - 1][j + (1 << (i-1))];
			if (h[me] <= h[oth])
				RMQ[i][j] = me;
			else
				RMQ[i][j] = oth;
		}
	}
	LOG[1] = 0;
	for (int i = 2; i <= cnt; i++)
		LOG[i] = LOG[i / 2] + 1;
	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: 18 / 18
• Subtask 3: 67 / 67