Submission #113508

#	Time	Username	Problem	Language	Result	Execution time	Memory
113508		AngusRitossa	Factories (JOI14_factories)	C++14	100 / 100	6943 ms	237748 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
	#define D(x...) printf(x)
#else
	#define D(x...)
#endif
typedef long long ll;
int n;
vector<pair<int, ll> > adj[500010];
int iscentroid[500010];
int seen[500010], upto;
int sz[500010];
ll closest[500010];
pair<int, ll> mycentroids[500010][20];
int findsz(int a, int p = -1)
{
	seen[a] = upto;
	sz[a] = 1;
	for (auto b : adj[a])
	{
		if (b.first != p && !iscentroid[b.first]) sz[a] += findsz(b.first, a);
	}
	return sz[a];
}	
ll len = 0;
void dfslen(int a, int c, int p = -1, ll len = 0)
{
	mycentroids[a][iscentroid[c]] = { c, len };
	D("%d belongs to %d, dis %lld\n", a, c, len);
	for (auto b : adj[a])
	{
		if (!iscentroid[b.first] && b.first != p)
		{
			dfslen(b.first, c, a, len+b.second);
		}
	}
}
int findcentroid(int a, int above = 0, int p = -1)
{
	if (!above) findsz(a);
	int sumchildren = above+1, mxchild = above;
	for (auto b : adj[a])
	{
		if (b.first != p && !iscentroid[b.first])
		{
			mxchild = max(mxchild, sz[b.first]);
			sumchildren += sz[b.first];
		}
	}
	if (mxchild <= (sumchildren)/2)
	{
		// is a centroid
		iscentroid[a] = upto;
		dfslen(a, a);
		return a;
	}
	for (auto b : adj[a])
	{
		if (b.first != p && !iscentroid[b.first] && sz[b.first] == mxchild)
		{
			return findcentroid(b.first, sumchildren-sz[b.first], a);
		}
	}
	assert(0); // what a shame
}

void Init(int N, int A[], int B[], int D[]) 
{
	n = N;
	for (int i = 0; i < n-1; i++)
	{
		adj[A[i]].emplace_back(B[i], D[i]);
		adj[B[i]].emplace_back(A[i], D[i]);
	}
	for (int i = 0; i < n; i++) fill_n(mycentroids[i], 20, make_pair(0, 1e15));
	for (int f = 0; f < 20; f++)
	{
		upto++;
		for (int i = 0; i < n; i++)
		{
			if (seen[i] != upto && !iscentroid[i])
			{
				findcentroid(i);
			}
		}
	}
	fill_n(closest, n, 1e15);
}
ll Query(int s, int x[], int t, int y[]) 
{
	ll ans = 1e15;
	for (int i = 0; i < s; i++) for (int j = 0; j < 20; j++) 
	{
		auto c = mycentroids[x[i]][j];
		closest[c.first] = min(closest[c.first], c.second);
	}
	for (int i = 0; i < t; i++) for (int j = 0; j < 20; j++) 
	{
		auto c = mycentroids[y[i]][j];
		ans = min(ans, closest[c.first]+c.second);
	}
	for (int i = 0; i < s; i++) for (int j = 0; j < 20; j++) 
	{
		auto c = mycentroids[x[i]][j];
		closest[c.first] = 1e15;
	}
	return ans;
}

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