Submission #890373

#	Time	Username	Problem	Language	Result	Execution time	Memory
890373		pan	Factories (JOI14_factories)	C++17	33 / 100	8100 ms	235444 KiB

factories

#ifndef FACTORIES_H_
#define FACTORIES_H_
#include <bits/stdc++.h>
//#include "bits_stdc++.h"
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
ll const MAXN = 500005;
ll sub[MAXN], lvl[MAXN], par[MAXN], m[MAXN], dist[MAXN];
vector<pi> V[MAXN];
ll twok[MAXN][25];
ll depth[MAXN];
ll n;
// 2k decomposition
void dfs(ll p, ll node)
{
	for (pi u: V[node])
	{
		if (p==u.f) continue;
		dist[u.f] = dist[node] + u.s;
		twok[u.f][0] = node;
		depth[u.f] = depth[node]+1;
		dfs(node, u.f);
	}
	
}
ll kpar(ll x, ll k)
{
	for (ll i=0; i<20; ++i)
	{
		if (k& (1<<i)) 
		{
			x=twok[x][i];
		}
	}
	return x;
}



ll lca(ll a, ll b)
{
	if (depth[a]<depth[b]) swap(a,b);
	a = kpar(a, depth[a]-depth[b]);
	if (a==b) return a;
	for (ll k=19; k>=0; k--)
	{
		if (twok[a][k]!=twok[b][k])
		{
			a=twok[a][k]; b = twok[b][k];
		}
	}
	return twok[a][0];
	
}

ll sp(ll a, ll b)
{
	return dist[a]+dist[b]-2*dist[lca(a,b)];
}

// centroid decomposition
ll dfs1(int u, int p, int l) {
	sub[u] = 1; // Subtree size is 1
	for (pi v : V[u]) {
		if (lvl[v.f] != -1) continue; // Already added to centroid tree
		if (v.f == p) continue;
		sub[u] += dfs1(v.f, u, l); // Increase size of subtree
	}
	return sub[u];
}
ll dfs2(int u, int p, int n) { // Pass in the size of the subtree
	for (pi v : V[u]) {
		if (lvl[v.f] != -1) continue; // Already added to centroid tree
		if (v.f != p && sub[v.f] > n / 2) {
			return dfs2(v.f, u, n); // DFS to that node
		}
	}
	return u; // No child has size more than n/2, hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u, int p, int l) {
	int n = dfs1(u, p, l); // Find the size of each subtree
	int cent = dfs2(u, p, n); // Find the centroid
	if (p == -1) p = cent; // Parent of root is yourself
	par[cent] = p; // Set the parent of centroid to the previous centroid
	lvl[cent] = l;
	for (pi v : V[cent]) {
		if (lvl[v.f] != -1) continue;
// If we have already added to centroid then we ignore
		build(v.f, cent, l + 1); // Recursively build each subtree
	}
}

//To construct the centroid tree, call build(root, -1, 0);



void Init(int N, int A[], int B[], int D[])
{
	n=N;
	for (ll i=0; i<n-1; ++i)
	{
		V[A[i]].pb(mp(B[i], D[i]));
		V[B[i]].pb(mp(A[i], D[i]));
	}
	dist[0]=0;
	depth[0] = 0;
	twok[0][0] = -1;
	dfs(-1,0);
	for (ll k=1; k<20; k++)
	{
		for (ll x=0; x<n; ++x)
		{
			if (twok[x][k-1]==-1) continue;
			twok[x][k] = twok[twok[x][k-1]][k-1];
		}
	}
	memset(lvl, -1, sizeof lvl);
	build(0, -1, 0);
	for (ll i=0; i<=n-1; ++i) {m[i]=LLONG_MAX;} // < n not <n-1
}


long long Query(int S, int X[], int T, int Y[])
{
	for (ll i=0; i<S; ++i)
	{
		ll nxt = X[i];
		m[nxt] = 0;
		while (par[nxt]!=nxt)
		{
			nxt = par[nxt];
			m[nxt] = min(m[nxt], sp(nxt, X[i]));
			//cout << "sp is " << sp(nxt, X[i]) << endl;
			//cout << "nxt become " << m[nxt] << endl;
		}
		
	}
	ll ans  = LLONG_MAX;
	for (ll i=0; i<T; ++i)
	{
		//cout << i << endl;
		ll nxt = Y[i];
		//cout << " nxt is " << nxt << endl;
		ans = min(ans, m[nxt]); // dont declare ans again
		//cout << "ans become " << ans << endl;
		while (par[nxt]!=nxt)
		{
			nxt = par[nxt];
			//cout << " go to " << nxt << endl;
			if (m[nxt]!=LLONG_MAX) {ans = min(ans, m[nxt] + sp(nxt, Y[i]));}
			//cout << "sp is " << sp(nxt, Y[i]) << endl;
			//cout << "ans become " << ans << endl;
		}
	}
	for (ll i=0; i<S; ++i)
	{
		ll nxt = X[i];
		m[nxt] = LLONG_MAX;
		while (par[nxt]!=nxt) {nxt = par[nxt]; m[nxt]=LLONG_MAX;}
	}
	//cout << "final ans is " << endl;
	return ans;
}

#endif  /* FACTORIES_H_ */

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