제출 #109276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109276		pamaj	공장들 (JOI14_factories)	C++14	100 / 100	7653 ms	206528 KiB

factories

#include <bits/stdc++.h>
#include"factories.h"
using namespace std;
using ii = pair<int, int>;

const int inf = 0x3f3f3f3f;
const int maxn  = 5e5 + 10, maxlog = 25;

typedef long long ll;

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

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

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

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

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

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

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

	return sz[x];
}

int tot;
ii best;

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

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

		heav = max(heav, sz[u.first]);

		split(u.first, 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;
	find_dist(best.first, -1, 0);

	for (auto u : G[cent]) {
		if (cvis[u.first]) continue;
		int p = solve(u.first);
		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: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67