Submission #311949

#	Time	Username	Problem	Language	Result	Execution time	Memory
311949		T0p_	Factories (JOI14_factories)	C++14	0 / 100	767 ms	524292 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define N 500500
#define pb push_back

struct GRAPH
{
	int node;
	long long weight;
};

int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N], dp[20][N];
bool visit[N];
vector<GRAPH> g[N];
queue<int> bt;

int get_sz(int u, int p)
{
	sz[u] = 1;
	for(auto x : g[u])
		if(visit[x.node] || x.node != p) sz[u] += get_sz(x.node, u);
	return sz[u];
}

int get_centroid(int u, int p, int n)
{
	bool ch = (n - sz[u] <= n/2) ? true : false;
	int nu = 0, nf = 0;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		if(sz[x.node] > n/2)
		{
			ch = false;
			if(sz[x.node] > nf)
			{
				nf = sz[x.node];
				nu = x.node;
			}
		}
	}
	return (ch) ? u : get_centroid(nu, u, n);
}

int build(int u, int p)
{
	int c = get_centroid(u, p, get_sz(u, p));
	visit[c] = true;
	for(auto x : g[c])
	{
		if(visit[x.node]) continue ;
		pa[build(x.node, c)] = c;
	}
	return c;
}

void dfs(int u, int l)
{
	lv[u] = l;
	for(auto x : g[u])
	{
		if(lv[x.node]) continue ;
		jmp_node[0][x.node] = u;
		jmp_dis[0][x.node] = x.weight;
		dfs(x.node, l+1);
	}
}

long long get_dis(int u, int v)
{
	long long ret = 0;
	if(lv[u] < lv[v]) swap(u, v);
	for(int i=19 ; i>=0 ; i--)
		if(lv[jmp_node[i][u]] >= lv[v])
		{
			ret += jmp_dis[i][u];
			u = jmp_node[i][u];
		}
	if(u == v) return ret;
	for(int i=19 ; i>=0 ; i--)
		if(jmp_node[i][u] != jmp_node[i][v])
		{
			ret += jmp_dis[i][u] + jmp_dis[i][v];
			u = jmp_node[i][u], v = jmp_node[i][v];
		}
	return ret + jmp_dis[0][u] + jmp_dis[0][v];
}

void Init(int n, int u[], int v[], int w[])
{
	for(int i=0 ; i<n-1 ; i++)
	{
		g[u[i]+1].pb({v[i]+1, w[i]});
		g[v[i]+1].pb({u[i]+1, w[i]});
	}
	dfs(1, 1);
	build(1, 0);
	for(int i=1 ; i<=n ; i++)
	{
		visit[i] = false;
		dis[i] = 1e15;
	}
	for(int i=1 ; i<20 ; i++)
		for(int j=1 ; j<=n ; j++)
		{
			jmp_node[i][j] = jmp_node[i-1][jmp_node[i-1][j]];
			jmp_dis[i][j] = jmp_dis[i-1][j] + jmp_dis[i-1][jmp_node[i-1][j]];
		}
	for(int i=1 ; i<=n ; i++)
	{
		int now = i;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			dp[j][i] = get_dis(i, now);
		}
	}
}

long long Query(int s, int x[], int t, int y[])
{
	long long ans = 1e15;
	for(int i=0 ; i<s ; i++)
	{
		int now = x[i]+1;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			if(!visit[now])
			{
				visit[now] = true;
				bt.push(now);
			}
			dis[now] = min(dis[now], dp[j][x[i]+1]);
		}
	}
	for(int i=0 ; i<t ; i++)
	{
		int now = y[i]+1;
		for(int j=0 ; true ; j++, now = pa[now])
		{
			assert(j <= 20);
			if(!now) break ;
			ans = min(ans, dis[now] + dp[j][y[i]+1]);
		}
	}
	while(!bt.empty())
	{
		visit[bt.front()] = false;
		dis[bt.front()] = 1e15;
		bt.pop();
	}
	return ans;
}

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