Submission #164573

#	Time	Username	Problem	Language	Result	Execution time	Memory
164573		faremy	Factories (JOI14_factories)	C++14	100 / 100	6150 ms	189680 KiB

factories

#include "factories.h"

#include <vector>


struct Edge
{
	Edge(int e, long long w) : end(e), weight(w) {}
	int end;
	long long weight;
};

const int MAXN = 5e5;
const int LOGN = 20;
const long long INFTY = 1e18;

std::vector<Edge> tree[MAXN];
bool seen[MAXN];
int size[MAXN];

int centrParent[MAXN], centrDepth[MAXN];
long long centrDist[MAXN][LOGN];

long long minActive[MAXN];


void calcsize(int node)
{
	seen[node] = true;
	size[node] = 1;

	for (Edge& edge : tree[node])
		if (!seen[edge.end])
		{
			calcsize(edge.end);
			size[node] += size[edge.end];
		}
	
	seen[node] = false;
}

int findcentr(int node, int treesize)
{
	if (seen[node])
		return 0;
	seen[node] = true;

	int maxSubSize = treesize - size[node];
	for (Edge &edge : tree[node])
	{
		int ans = findcentr(edge.end, treesize);
		if (ans < 0)
		{
			seen[node] = false;
			return ans;
		}

		maxSubSize = std::max(maxSubSize, ans);
	}

	seen[node] = false;
	if (maxSubSize <= treesize / 2)
		return (-1 - node);
	return size[node];
}

void calcdist(int node, long long dist)
{
	if (seen[node])
		return;
	seen[node] = true;

	centrDist[node][centrDepth[node]] = dist;
	centrDepth[node]++;

	for (Edge &edge : tree[node])
		calcdist(edge.end, dist + edge.weight);
	seen[node] = false;
}

void buildcentr(int node, int parent)
{
	calcsize(node);
	int centroid = (-1 - findcentr(node, size[node]));

	centrParent[centroid] = parent;
	seen[centroid] = true;

	for (Edge &edge : tree[centroid])
		if (!seen[edge.end])
			buildcentr(edge.end, centroid);

	seen[centroid] = false;
	calcdist(centroid, 0);
	minActive[centroid] = INFTY;
}

void Init(int N, int A[], int B[], int D[])
{
	for (int iEdge = 0; iEdge < N - 1; iEdge++)
	{
		tree[A[iEdge]].emplace_back(B[iEdge], D[iEdge]);
		tree[B[iEdge]].emplace_back(A[iEdge], D[iEdge]);
	}

	buildcentr(0, -1);
}

long long Query(int S, int X[], int T, int Y[])
{
	for (int iNode = 0; iNode < S; iNode++)
	{
		int ancester = X[iNode];
		for (int iAnc = 0; iAnc < centrDepth[X[iNode]]; iAnc++)
		{
			minActive[ancester] = std::min(minActive[ancester], centrDist[X[iNode]][iAnc]);
			ancester = centrParent[ancester];
		}
	}

	long long minDist = INFTY;
	for (int iNode = 0; iNode < T; iNode++)
	{
		int ancester = Y[iNode];
		for (int iAnc = 0; iAnc < centrDepth[Y[iNode]]; iAnc++)
		{
			minDist = std::min(minDist, minActive[ancester] + centrDist[Y[iNode]][iAnc]);
			ancester = centrParent[ancester];
		}
	}

	for (int iNode = 0; iNode < S; iNode++)
		for (int ancester = X[iNode]; ancester != -1; ancester = centrParent[ancester])
			minActive[ancester] = INFTY;

	return minDist;
}

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