Submission #109255

#	Time	Username	Problem	Language	Result	Execution time	Memory
109255		pamaj	Factories (JOI14_factories)	C++14	100 / 100	6759 ms	179780 KiB

factories

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

#pragma GCC optimize ("Ofast")

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

int pai[maxn], h[maxn], block[maxn], sz[maxn];
ll ans[maxn];
ll dist[maxn][maxlog];
vector<pair<int, int>> G[maxn]; 
vector<int> 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];
	}
}

void find_dist(int v, int p, ll depht)
{
	dist[v][h[v]++] = depht;

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

		find_dist(u.first, v, depht + u.second);
	}
}

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

	find_dist(centro, -1, 0);

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

	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[])
{
	for(int i = 0; i < S; i++)
	{
		int v = X[i];

		int x = v;

		for(int j = h[x] - 1; j >= 0; j--)
		{
			ans[v] = min(ans[v], dist[x][j]);
			v = pai[v];
 		}
	}

	ll resp = 1e16;

	for(int i = 0; i < T; i++)
	{
		int v = Y[i];

		int x = v;

		for(int j = h[x] - 1; j >= 0; j--)
		{
			resp = min(resp, ans[v] + dist[x][j]);
			v = pai[v];
		}
	}

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

		int x = v;

		for(int j = h[x] - 1; j >= 0; j--)
		{
			ans[x] = 1e16;

			x = pai[x];
		}
	}
	return resp;
}

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