Submission #387658

#	Time	Username	Problem	Language	Result	Execution time	Memory
387658		wind_reaper	Factories (JOI14_factories)	C++17	0 / 100	35 ms	14540 KiB

factories

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

using namespace std;

const int MXN = 500001;
const int lg = 20;
const int64_t INF = 1e18;

int up[lg][MXN], tin[MXN], tout[MXN], timer = 0;
int64_t dist[MXN];

int par[MXN], sz[MXN], depth[MXN], r[MXN];
int64_t best[MXN];

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

// vector<int> hit;
int hit[4*MXN], ptr = 0;

void dfs(int node, int p, int dis){
	tin[node] = timer++;
	dist[node] = dist[p] + int64_t(dis);
	
	up[0][node] = p;
	for(int i = 1; i < lg; i++)
		up[i][node] = up[i-1][up[i-1][node]];

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

	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 = lg-1; i >= 0; --i){
		if(!isAncestor(up[i][u], v))
			u = up[i][u];
	}

	return up[0][u];
}

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

int centroid(int node, int ms, int p){
	for(auto& [v, d] : g[node])
		if(!r[v] && v != p && sz[v]*2 > ms)
			return centroid(v, ms, node);

	return node;
}

int subtreedfs(int node, int p){
	if(r[node]) return sz[node] = 0;

	sz[node] = 1;
	for(auto& [v, d] : g[node]){
		if(r[v] == 0 && v != p)
			sz[node] += subtreedfs(v, node);
	}

	return sz[node];
}

void decompose(int node, int p){
	int ms = subtreedfs(node, -1);
	int c = centroid(node, p, ms);
	r[c] = 1;
	par[c] = p;
	for(auto& [v, d] : g[c]){
		if(r[v] == 0)
			decompose(v, c);
	}
}

void update(int node){
	int v = node;
	while(v != -1){
		best[v] = min(best[v], distance(v, node));
		hit[ptr++] = v;
		v = par[v];
	}
}

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

void Init(int n, int A[], int B[], int D[]){
	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]});
	}

	memset(par, -1, sizeof par);
	
	for(int i = 0; i < n; i++)
		best[i] = INF;

	dfs(0, 0, 0);
	decompose(0, -1);
}


long long Query(int S, int X[], int T, int Y[]){
	while(ptr)
		best[hit[ptr--]] = INF;
	
	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]));
	return ans;
}

#ifdef LOCAL
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int N, Q;
	cin >> N >> Q;
	int A[N-1], B[N-1], D[N-1];

	for(int i = 0; i < N-1; i++){
		cin >> A[i] >> B[i] >> D[i];
	}
	
	Init(N, A, B, D);
	
	for(int i = 0; i < Q; i++){
		int S, T;
		cin >> S >> T;
		int X[S], Y[T];
		for(int j = 0; j < S; j++)
			cin >> X[j];
		for(int j = 0; j < T; j++)
			cin >> Y[j];

		cout << Query(S, X, T, Y) << '\n';
	}

	return 0; 
}
#endif

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