Submission #98910

#	Time	Username	Problem	Language	Result	Execution time	Memory
98910		pamaj	Factories (JOI14_factories)	C++17	15 / 100	8023 ms	183148 KiB

factories

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

#pragma GCC optimize ("Ofast")

const int maxn  = 5e5 + 10, maxlog = 19;

ll pai[maxn], h[maxn], block[maxn], sz[maxn], anc[maxn][maxlog], dist[maxn], ans[maxn];

vector<pair<ll, ll>> G[maxn]; 
vector<ll> tree[maxn], lista;

void dfs(int x, int p)
{
	pai[x] = p;

	sz[x] = 1;

	lista.push_back(x);

	for(auto u : G[x])
	{
		int v = u.first;
		if(block[v] or v == p) continue;

		dfs(v, x);

		sz[x] += sz[v];
	}
}

int find_centroid(int x)
{
	lista.clear();

	dfs(x, x);

	int centro = x;

	int qt = sz[x];

	for(auto u : lista)
	{
		bool ok = true;
		if(qt - sz[u] > qt/2) ok = false;

		for(auto v : G[u])
		{
			int at = v.first;

			if(block[at] or pai[u] == at) continue;

			if(sz[at] > qt/2) ok = false;
		}

		if(ok) centro = u;
	}

	return centro;
}

int build(int x)
{
	x = find_centroid(x);

	block[x] = true;

	for(auto u : G[x])
	{
		int at = u.first;
		if(block[at]) continue;

		int v = build(at);

		tree[x].push_back(v);
		tree[v].push_back(x);
	}

	return x;
}

void ancestor(int x, int p)
{
	h[x] = h[p] + 1;

	for(auto v : G[x])
	{
		int u = v.first;
		if(u == p) continue;

		anc[u][0] = x;

		for(int i = 1; i < maxlog; i++)
			anc[u][i] = anc[anc[u][i - 1]][i - 1];

		dist[u] = dist[x] + v.second;
		ancestor(u, x); 
	}
}

int lca(int x, int y)
{
	if(x == y) return x;
	if(h[y] < h[x]) swap(x, y);

	for(int i = maxlog - 1; i >= 0 and h[x] != h[y]; i--)
		if((h[y] - (1 << i)) >= h[x])
			y = anc[y][i];
	
	if(x == y) return x;

	for(int i = maxlog - 1; i >= 0; i--)
	{
		if(anc[y][i] != 0 and anc[x][i] != 0 and anc[x][i] != anc[y][i])
		{
			x = anc[x][i], y = anc[y][i];
		}
	}

	if(x == y) return x;
	return anc[x][0];
}

void init(int x, int p)
{
	pai[x] = p;

	for(auto u : tree[x])
	{
		if(u == p) continue;
		init(u, x);
	}
}

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]});
	}

	int ct = build(1);

	ancestor(ct, ct);

	init(ct, -1);

	for(int i = 0; i < maxn; i++) ans[i] = (long long)1e17;
}

long long Query(int S, int X[], int T, int Y[])
{
	bool ok = false;

	if(2*S > T) swap(S, T), ok = true;

	for(int i = 0; i < S; i++)
	{
		int at = X[i];

		if(ok) at = Y[i];

		int node = at;

		while(node != -1)
		{
			int LCA = lca(node, at);

			ans[node] = min(ans[node], dist[node] + dist[at] - 2*dist[LCA]);

			node = pai[node];
		}
	}

	ll resp = 1e16;
	for(int i = 0; i < T; i++)
	{
		int at = Y[i];

		if(ok) at = X[i];

		int node = at;

		while(node != -1)
		{
			int LCA = lca(node, at);

			resp = min(resp, ans[node] + dist[node] + dist[at] - 2*dist[LCA]);

			node = pai[node];

		}
	}

	for(int i = 0; i < S; i++)
	{
		int at = X[i];

		if(ok) at = Y[i];

		int node = at;
		while(node != -1)
		{
			ans[node] = 1e16;

			node = pai[node];

		}
	}
	return resp;
}

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