Submission #97042

#	Time	Username	Problem	Language	Result	Execution time	Memory
97042		luciocf	Factories (JOI14_factories)	C++14	15 / 100	8061 ms	97100 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][20], nivel[maxn];
int sz[maxn], pai[maxn];
int x[maxn], y[maxn];

ll dist[maxn], child[maxn];

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

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

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

	if (u == v) return u;

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

	return tab[u][0];
}

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

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

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

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

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

	for (int i = 0; i < s; i++)
		x[i] = X[i];
	for (int i = 0; i < t; i++)
		y[i] = Y[i];

	vector<int> vis;

	for (int i = 0; i < t; i++)
	{
		int v = y[i];

		while (v != -1)
		{
			vis.push_back(v);

			ll d = dist[y[i]]+dist[v]-2LL*dist[lca(y[i], v)];

			child[v] = min(child[v], d);

			v = pai[v];
		}
	}

	ll ans = inf;

	for (int i = 0; i < s; i++)
	{
		int v = x[i];

		while (v != -1)
		{
			ll d = dist[x[i]]+dist[v]-2LL*dist[lca(x[i], v)];

			ans = min(ans, d+child[v]);

			v = pai[v];
		}
	}

	for (auto x: vis) child[x] = inf;

	return ans;
}

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