Submission #1128479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128479		Nonoze	Factories (JOI14_factories)	C++20	15 / 100	8095 ms	279112 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define cmin(a, b) a = min(a, b)
const int inf = 1e18;

const int LOG=20;


int n;
vector<vector<pair<int, int>>> adj, up;
vector<int> depth;

void dfsinit(int u, int p) {
	for (auto [v, w]: adj[u]) if (v!=p) {
		up[v][0]={u, w};
		for (int i=1; i<LOG; i++) {
			if (up[v][i-1].fi==-1) break;
			up[v][i]=up[up[v][i-1].fi][i-1];
			up[v][i].se+=up[v][i-1].se;
		}
		depth[v]=depth[u]+1;
		dfsinit(v, u);
	}
}

pair<int, int> lca(int a, int b) {
	if (a==b) return {a, 0};
	if (depth[a]<depth[b]) swap(a, b);
	int ans=0;
	int k=depth[a]-depth[b];
	for (int i=0; i<LOG; i++) if (k&(1<<i)) ans+=up[a][i].se, a=up[a][i].fi;
	if (a==b) return {a, ans};
	for (int i=LOG-1; i>=0; i--) if (up[a][i].fi!=up[b][i].fi) {
		ans+=up[a][i].se+up[b][i].se;
		a=up[a][i].fi, b=up[b][i].fi;
	}
	return {up[a][0].fi, ans+up[a][0].se+up[b][0].se};
}

int dist(int a, int b) {
	return lca(a, b).se;
}


vector<int> sz, centro, par;

void dfs(int u, int p) {
	sz[u]=1;
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		dfs(v, u);
		sz[u]+=sz[v];
	}
}

int centroid(int u, int p, int obj) {
	for (auto [v, w]: adj[u]) if (v!=p && !centro[v]) {
		if (sz[v]*2>=obj) return centroid(v, u, obj);
	}
	return u;
}

int decompose(int u, int p) {
	if (centro[u]) return u;
	dfs(u, u);
	int c=centroid(u, u, sz[u]); centro[c]=1;
	par[c]=p;
	for (auto [v, w]: adj[c]) if (!centro[v]) {
		decompose(v, c);
	}
	return c;
}

vector<int> distres;

void update(int u, int changing=-1) {
	if (changing==-1) changing=u;
	if (u==-1) return;
	cmin(distres[u], dist(u, changing));
	update(par[u], changing);
}

void reset(int u, int changing=-1) {
	if (changing==-1) changing=u;
	if (u==-1) return;
	distres[u]=inf;
	reset(par[u], changing);
}

int query(int u, int changing=-1) {
	if (changing==-1) changing=u;
	if (u==-1) return inf;
	return min(distres[u]+dist(u, changing), query(par[u], changing));
}

void Init(signed N, signed A[], signed B[], signed D[]) {
	n=N;
	adj.resize(n);
	for (int i=0; i<n-1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	up.resize(n, vector<pair<int, int>>(LOG, {-1, 0}));
	depth.resize(n), sz.resize(n), centro.resize(n), par.resize(n, -1);
	dfsinit(0, 0);
	decompose(0, -1);
	distres.resize(n, inf);
}

int Query(signed S, signed X[], signed T, signed Y[]) {
	int ans=inf;
	for (int i=0; i<S; i++) update(X[i]);
	for (int i=0; i<T; i++) cmin(ans, query(Y[i]));
	for (int i=0; i<S; i++) reset(X[i]);
	return ans;
}

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