Submission #993787

#	Time	Username	Problem	Language	Result	Execution time	Memory
993787		Error42	Factories (JOI14_factories)	C++17	100 / 100	3451 ms	367416 KiB

factories

#include "factories.h"

#include <climits>
#include <vector>

using namespace std;

using ll = long long;

#define int ll

ll const INF = LLONG_MAX / 3;

struct edge {
	ll to, dist;
};

ll n;

ll cur_dist = 0;
vector<vector<edge>> ancestors;
vector<vector<edge>> graph;
vector<ll> sz;
vector<char> removed;
vector<ll> min_dist;

void calc_sz(int const cur, int const par) {
	sz[cur] = 1;

	for (auto const& [neigh, _dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		calc_sz(neigh, cur);
		sz[cur] += sz[neigh];
	}
}

int get_centroid(int const cur, int const par, int const tree_sz) {
	for (auto const& [neigh, _dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		if (sz[neigh] > tree_sz / 2)
			return get_centroid(neigh, cur, tree_sz);
	}

	return cur;
}

void calc_ancestors(int const cur, int const par, int const centroid) {
	ancestors[cur].push_back({ centroid, cur_dist });

	for (auto const& [neigh, dist] : graph[cur]) {
		if (removed[neigh] || neigh == par)
			continue;

		cur_dist += dist;
		calc_ancestors(neigh, cur, centroid);
		cur_dist -= dist;
	}
}

void decompose(int const cur) {
	calc_sz(cur, -1);
	int const centroid = get_centroid(cur, -1, sz[cur]);
	calc_ancestors(centroid, -1, centroid);
	removed[centroid] = true;
	
	for (auto const& [neigh, _dist] : graph[centroid]) {
		if (removed[neigh])
			continue;

		decompose(neigh);
	}
}

void Init(signed const N, signed a[], signed b[], signed d[]) {
	n = N;

	graph.resize(n);
	sz.resize(n);
	removed.resize(n);
	ancestors.resize(n);
	min_dist.assign(n, INF);

	for (int i = 0; i < n - 1; i++) {
		graph[a[i]].push_back({ b[i], d[i] });
		graph[b[i]].push_back({ a[i], d[i] });
	}

	decompose(0);
}

ll Query(signed const s, signed x[], signed const t, signed y[]) {
	for (int i = 0; i < t; i++) {
		int const cur = y[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			min_dist[ancestor] = min(min_dist[ancestor], dist);
		}
	}

	ll ans = INF;
	
	for (int i = 0; i < s; i++) {
		int const cur = x[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			ans = min(ans, min_dist[ancestor] + dist);
		}
	}

	for (int i = 0; i < t; i++) {
		int const cur = y[i];

		for (auto const& [ancestor, dist] : ancestors[cur]) {
			min_dist[ancestor] = INF;
		}
	}

	return ans;
}

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