Submission #1224138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224138		colossal_pepe	Factories (JOI14_factories)	C++20	100 / 100	2766 ms	241432 KiB

factories

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

using ll = long long;

const ll INF = 1e18;

int n;
vector<vector<pair<int, ll>>> t;
vector<vector<pair<int, ll>>> dist;
vector<ll> min_dist;

int decompose(int s, int depth, vector<int> &subt_n, vector<bool> &done) {
	auto dfs1 = [s, &done, &subt_n](const auto &self, int u, int par) -> void {
		subt_n[u] = 1;
		for (auto [v, d] : t[u]) {
			if (done[v] or v == par) continue;
			self(self, v, u);
			subt_n[u] += subt_n[v];
		}
	};
	dfs1(dfs1, s, -1);
	int cn = subt_n[s];

	auto dfs2 = [cn, &done, &subt_n](const auto &self, int u, int par) -> int {
		for (auto [v, d] : t[u]) {
			if (done[v] or v == par) continue;
			if (subt_n[v] * 2 > cn) return self(self, v, u);
		}
		return u;
	};
	int c = dfs2(dfs2, s, -1);

	done[c] = 1;
	dist[c][depth] = make_pair(c, 0);
	auto dfs3 = [c, depth, &done](const auto &self, int u, int par) -> void {
		for (auto [v, d] : t[u]) {
			if (done[v] or v == par) continue;
			dist[v][depth] = make_pair(c, dist[u][depth].second + d);
			self(self, v, u);
		}
	};
	dfs3(dfs3, c, -1);

	for (auto [v, d] : t[c]) {
		if (done[v]) continue;
		decompose(v, depth + 1, subt_n, done);
	}
	return c;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	t.resize(n);
	for (int i = 0; i < n - 1; i++) {
		t[A[i]].push_back(make_pair(B[i], D[i]));
		t[B[i]].push_back(make_pair(A[i], D[i]));
	}
	dist.resize(n, vector<pair<int, ll>>(19, make_pair(-1, INF)));
	vector<int> subt_n(n, 0);
	vector<bool> done(n, 0);
	decompose(0, 0, subt_n, done);
	min_dist.resize(n, INF);
}

ll Query(int S, int X[], int T, int Y[]) {
	for (int i = 0; i < T; i++) {
		for (auto [v, d] : dist[Y[i]]) {
			if (v == -1) break;
			min_dist[v] = min(min_dist[v], d);
		}
	}
	ll ret = INF;
	for (int i = 0; i < S; i++) {
		for (auto [v, d] : dist[X[i]]) {
			if (v == -1) break;
			ret = min(ret, d + min_dist[v]);
		}
	}
	for (int i = 0; i < T; i++) {
		for (auto [v, d] : dist[Y[i]]) {
			if (v == -1) break;
			min_dist[v] = INF;
		}
	}
	return ret;
}

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