Submission #577932

#	Time	Username	Problem	Language	Result	Execution time	Memory
577932		M_W	Factories (JOI14_factories)	C++17	0 / 100	22 ms	25044 KiB

factories

#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int up[21][500001], lg, timer = 0;
int tin[500001], tout[500001]; 
long long dist[500001];
vector<ii> adj[500001];

// LCA stuff

void process_lca(int a, int p){
	tin[a] = timer++;
	for(int i = 1; i <= lg; i++){
		up[a][i] = up[up[a][i - 1]][i - 1];
	}
	
	for(auto [x, w] : adj[a]){
		if(x == p) continue;
		dist[x] = dist[a] + w;
		process_lca(x, a);
	}
	tout[a] = timer++;
}

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

int lca(int u, int v){
	if(is_an(v, u)) return v;
	for(int i = lg; i >= 0; i--){
		if(!is_an(u, v)) u = up[u][i];
	}
	return up[u][0];
}

long long get_dist(int u, int v){
	int lca_uv = lca(u, v);
	return - (dist[lca_uv] << 1) + (dist[u] + dist[v]);
}

// Centroid stuff

bool blocked[500001];
int sz[500001], split_node;

int calc_subtree(int a, int p){
	sz[a] = 1;
	for(auto [x, w] : adj[a]){
		if(x == p || blocked[x]) continue;
		sz[a] += calc_subtree(x, a);
	}
	return sz[a];
}

bool get_split(int a, int p, int rt){
	int msz = sz[rt] - sz[a];
	for(auto [x, w] : adj[a]){
		if(x == p || blocked[x]) continue;
		msz = max(msz, sz[x]);
		if(get_split(x, a, rt)) return true;
	}
	if(msz <= sz[rt] >> 1){
		split_node = a;
		return true;
	}
	return false;
}

int pa[500001];

void build_tree(int a, int p){
	calc_subtree(a, p);
	get_split(a, p, a);
	
	pa[split_node] = p;
	blocked[split_node] = true;
	for(auto [x, w] : adj[split_node]){
		if(blocked[x]) continue;
		build_tree(x, split_node);
	}
}

// Actual Problem

int bk[500001], book = 1;
long long d[500001];

void update(int u){
	int tmp_u = u;
	while(u != -1){
		if(bk[u] < book) d[u] = get_dist(tmp_u, u);
		else d[u] = min(d[u], get_dist(tmp_u, u));
		bk[u] = book;
		u = pa[u];
	}
}

long long query(int v){
	int tmp_v = v; long long ret = LLONG_MAX;
	while(v != -1){
		if(bk[v] == book) ret = min(ret, d[v] + get_dist(tmp_v, v));
		v = pa[v];
	}
	return ret;
}

// Functions

void Init(int N, int* A, int* B, int* D){
	lg = int(ceil(log2(N)));
	
	for(int i = 0; i < N - 1; i++){
		adj[A[i]].push_back({B[i], D[i] * 1ll});
		adj[B[i]].push_back({A[i], D[i] * 1ll});
	}
	process_lca(0, -1);
	build_tree(0, -1);
}

long long Query(int S, int* X, int T, int* Y){
	long long ans = LLONG_MAX;
	for(int i = 0; i < S; i++) update(X[i]);
	for(int j = 0; j < T; j++) ans = min(ans, query(Y[j]));
	book++;
	return ans;
}

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