Submission #97061

#	Time	Username	Problem	Language	Result	Execution time	Memory
97061		luciocf	Factories (JOI14_factories)	C++14	15 / 100	8067 ms	206560 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

#define ff first
#define ss second

using namespace std;

const int maxn = 5e5+10;
const long long inf = 1e18+10;

typedef pair<int, int> pii;
typedef long long ll;

int n;
int tab[maxn][19], anc[maxn][19], nivel[maxn];
int sz[maxn], pai[maxn];

ll dist[maxn], child[maxn], D[maxn][19];

bool mark[maxn];

vector<pii> grafo[maxn];

void dfs(int u, int p)
{
	for (auto pp: grafo[u])
	{
		int v = pp.ff, d = pp.ss;

		if (v == p) continue;

		tab[v][0] = u, nivel[v] = nivel[u]+1;
		dist[v] = dist[u]+(ll)d;

		dfs(v, u);
	}
}

int dfs2(int u, int p)
{
	sz[u] = 1;
	for (auto pp: grafo[u])
	{
		int v = pp.ff;
		if (v == p || mark[v]) continue;

		sz[u] += dfs2(v, u);
	}

	return sz[u];
}

int centroid(int S, int u, int p)
{
	for (auto pp: grafo[u])
	{
		int v = pp.ff;
		if (v == p || mark[v]) continue;

		if (sz[v] > S/2) return centroid(S, v, u);
	}

	return u;
}

int decompose(int u)
{
	dfs2(u, -1);

	int c = centroid(sz[u], u, -1);
	mark[c] = 1;

	for (auto pp: grafo[c])
	{
		int v = pp.ff;
		if (mark[v]) continue;

		int c2 = decompose(v);

		pai[c2] = c;
	}

	return c;
}

void build_lca(void)
{
	for (int j = 1; j < 19; j++)
		for (int i = 0; i < n; i++)
			if (tab[i][j-1] != -1)
				tab[i][j] = tab[tab[i][j-1]][j-1];
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = 18; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i];

	if (u == v) return u;

	for (int i = 18; i >= 0; i--)
		if (tab[u][i] != -1 && tab[v][i] != -1 && tab[u][i] != tab[v][i])
			u = tab[u][i], v = tab[v][i];

	return tab[u][0];
}

void build_dist(void)
{
	for (int i = 0; i < n; i++)
	{
		int v = i, up = 0;
		while (v != -1)
		{
			D[i][up] = dist[i]+dist[v]-2LL*dist[lca(v, i)];
			anc[i][up] = v;

			v = pai[v], up++;
		}
	}
}

void Init(int N, int A[], int B[], int D[])
{
	n = N;

	for (int i = 0; i < n-1; i++)
	{
		grafo[A[i]].push_back({B[i], D[i]});
		grafo[B[i]].push_back({A[i], D[i]});
	}

	memset(pai, -1, sizeof pai);
	memset(tab, -1, sizeof tab);
	memset(anc, -1, sizeof anc);

	for (int i = 0; i < n; i++)
		child[i] = inf;

	dfs(0, -1); decompose(0);

	build_lca(); build_dist();
}

long long Query(int S, int X[], int T, int Y[])
{
	int s = S, t = T;

	for (int i = 0; i < t; i++)
	{
		for (int up = 0; up < 20; up++)
		{
			int v = anc[Y[i]][up];
			if (v == -1) break;

			child[v] = min(child[v], D[Y[i]][up]);
		}
	}

	ll ans = inf;

	for (int i = 0; i < s; i++)
	{
		for (int up = 0; up < 20; up++)
		{
			int v = anc[X[i]][up];
			if (v == -1) break;

			ans = min(ans, D[X[i]][up]+child[v]);
		}
	}

	for (int i = 0; i < t; i++)
	{
		for (int up = 0; up < 20; up++)
		{
			int v = anc[Y[i]][up];
			if (v == -1) break;

			child[v] = inf;
		}
	}

	return ans;
}

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