Submission #383961

#	Time	Username	Problem	Language	Result	Execution time	Memory
383961		wind_reaper	Factories (JOI14_factories)	C++17	0 / 100	8016 ms	12908 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int MXN = 500000;
const int LOG = 20;
const int64_t INF = 1e18;

vector<array<int, 2>> g[MXN];
int sz[MXN], centroid[MXN], up[LOG][MXN], tin[MXN], tout[MXN];
int64_t depth[MXN], best[MXN];
vector<bool> vis(MXN, 0);

int timer = 0;

void dfs(int node, int par, int dist){
	tin[node] = timer++;
	depth[node] = depth[par] + int64_t(dist);

	up[0][node] = par;
	for(int i = 1; i < LOG; i++)
		up[i][node] = up[i-1][up[i-1][node]];

	for(auto& [v, d] : g[node]){
		if(v == par)
			continue;
		dfs(v, node, d);
		sz[node] += sz[v];
	}

	tout[node] = timer;
}

inline bool isAncestor(int u, int v){
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v){
	if(isAncestor(u, v))
		return u;
	if(isAncestor(v, u))
		return v;

	for(int i = LOG-1; i >= 0; --i){
		if(!isAncestor(up[i][u], v))
			u = up[i][u];
	}

	return up[0][u];
}

inline int64_t dist(int u, int v){
	return depth[u] + depth[v] - 2*depth[lca(u, v)];
}

void decompose(int node, int c){
	int inv = -1, szl = (sz[node] >> 1);
	for(auto& [v, d] : g[node]){
		if(!vis[v] && sz[v] > szl){
			inv = v;
			break;
		}
	}

	if(inv != -1){
		sz[node] -= sz[inv];
		sz[inv] += sz[node];
		return decompose(inv, c);
	}

	vis[node] = 1;
	centroid[node] = c;

	for(auto& [v, d] : g[node]){
		if(!vis[v]){
			centroid[v] = node;
			decompose(v, node);
		}
	}
}

vector<int> hit; 
void update(int node){
	int v = node;
	while(v != -1){
		best[v] = min(best[v], dist(node, v));
		hit.push_back(v);
		v = centroid[v];
	}
}

int64_t query(int node){
	int64_t ans = INF;
	int v = node;
	while(v != -1){
		ans = min(ans, best[v] + dist(v, node));
	}
	return ans;
}

void Init(int n, int A[], int B[], int D[]){
	for(int i = 0; i < n; i++)
		best[i] = INF;

	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, 0, 0);
	decompose(0, -1);
}

long long Query(int S, int X[], int T, int Y[]){
	for(int i = 0; i < S; i++)
		update(X[i]);
	int64_t ans = INF;
	for(int i = 0; i < T; i++)
		ans = min(ans, query(Y[i]));
	
	for(int i : hit)
		best[i] = INF;
	hit.clear();
	return ans;
}

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