Submission #383942

#	Time	Username	Problem	Language	Result	Execution time	Memory
383942		wind_reaper	Factories (JOI14_factories)	C++17	15 / 100	8034 ms	117944 KiB

factories

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

using namespace std;

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

vector<array<int, 2>> g[N];

struct LCA{
	int tin[N], tout[N], up[LOG][N];
	int64_t depth[N];
	int timer = 0;

	void init(){
		dfs();
	}

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

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

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

		tout[node] = timer;
	}

	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];
	}

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

struct CentroidDecomposition{
	bool vis[N];
	vector<int> hit;
	int sz[N], par[N];
	int64_t best[N];

	LCA S;

	void init(int s, int A[], int B[], int D[]){
		memset(sz, 0, sizeof sz);
		memset(par, 0, sizeof par);
		
		for(int i = 0; i < s; i++)
			best[i] = INF;

		for(int i = 0; i < s-1; i++){
			g[A[i]].push_back({B[i], D[i]});
			g[B[i]].push_back({A[i], D[i]});
		}

		S.init();
		tree();
	}

	int find(int node, int p = -1){
		if(vis[node]) return 0;
		sz[node] = 1;
		for(auto& [v, d] : g[node]){
			if(v != p)
				sz[node] += find(v, node);
		}
		return sz[node];
	}

	int centroid(int node, int p, int n){
		for(auto& [v, d] : g[node]){
			if(v == p)
				continue;
			if(!vis[v] && sz[v] > n / 2)
				return centroid(v, node, n);
		}

		return node;
	}

	void tree(int node = 0, int p = -1){
		find(node);

		int c = centroid(node, -1, sz[node]);
		vis[c] = true;
		par[c] = p;

		for(auto& [v, d] : g[c]){
			if(!vis[v])
				tree(v, c);
		}
	}

	void update(int node){
		int u = node;
		while(u != -1){
			best[u] = min(best[u], S.dist(u, node));
			hit.push_back(u);
			u = par[u];
		}
	}

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

	void reset(){
		for(int i : hit)
			best[i] = INF;
		hit.clear();
	}
}D;

void Init(int n, int A[], int B[], int d[]){
	D.init(n, A, B, d);
}

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

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