Submission #109260

#	Time	Username	Problem	Language	Result	Execution time	Memory
109260		pamaj	Factories (JOI14_factories)	C++14	0 / 100	42 ms	39800 KiB

factories

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

#pragma GCC optimize ("Ofast")

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

int pai[maxn], h[maxn], block[maxn], last[maxn];
ll ans[maxn], dist[maxn][maxlog];
vector<pair<int, int>> G[maxn]; 
vector<int> tree[maxn], lista;

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);
	}
}
using ii = pair<int, int>;

const int inf = 0x3f3f3f3f;

int n, k;
vector<int> v[maxn];

int sz[maxn];
int cvis[maxn];

int tam(int x, int p)
{
	sz[x] = 1;

	for (int u : v[x]) {
		if (cvis[u] or u == p) continue;

		sz[x] += tam(u, x);
	}

	return sz[x];
}

int tot;
ii best;

void split(int x, int p)
{
	int heav = tot - sz[x];

	for (int u : v[x]) {
		if (cvis[u] or u == p) continue;

		heav = max(heav, sz[u]);
		split(u, x);
	}

	if (best.second > heav) best = {x, heav};
}

int centroid(int x)
{
	tot = tam(x, x);
	best = {0, inf};
	split(x, x);
	return best.first;
}

int solve(int x)
{
	int cent = centroid(x);
	cvis[cent] = 1;

	for (int u : v[cent]) {
		if (cvis[u]) continue;
		int p = solve(u);
		tree[cent].push_back(p);
		tree[p].push_back(cent);
	}

	return cent;
}

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 = solve(1);

	init(ct, -1);

	for(int i = 0; i < maxn; i++) ans[i] = (long long)1e17;
}

int it;

long long Query(int S, int X[], int T, int Y[])
{
	it++;
	for(int i = 0; i < S; i++)
	{
		int v = X[i];

		int x = v;

		for(int j = h[x] - 1; j >= 0; j--)
		{
			if(last[v] != it)
			{
				last[v] = it;
				ans[v] = dist[x][j];
			}
			else 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--)
		{
			if(last[v] == it) resp = min(resp, ans[v] + dist[x][j]);
			v = pai[v];
		}
	}
	return resp;
}

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