Submission #88121

#	Time	Username	Problem	Language	Result	Execution time	Memory
88121		KCSC	Factories (JOI14_factories)	C++14	33 / 100	8013 ms	202216 KiB

factories

#ifndef HOME
	#include "factories.h"
#endif

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

const int LOG = 21;
const int DIM = 500005;

int lev[DIM], szt[DIM], par[DIM], rmq[DIM << 1][LOG], pwr[DIM << 1], pos[DIM];
long long dst[DIM], dp[DIM]; vector<pair<int, int>> edg[DIM]; bool oki[DIM];

void dfs(int x, int f, int d) {
	static int nr = 0;
	dst[x] = dst[f] + d; rmq[++nr][0] = x;   
	lev[x] = lev[f] + 1; pos[x] = nr;
	for (auto &ed : edg[x]) {
		int y = ed.first, c = ed.second;
		if (y != f) {
			dfs(y, x, c); rmq[++nr][0] = x; } } } 

void getCentroid(int x, int f, int sz, int &c) {
	int mx = 0; szt[x] = 1;
	for (auto &ed : edg[x]) {
		int y = ed.first;
		if (!oki[y] and y != f) {
			getCentroid(y, x, sz, c); szt[x] += szt[y];
			mx = max(mx, szt[y]); } }
	mx = max(mx, sz - szt[x]);
	if (mx <= sz / 2) {	
		c = x; } }

void buildRmq(int n) {
	for (int i = 2; i <= n; ++i) {
		pwr[i] = pwr[i >> 1] + 1; }
	for (int k = 1; (1 << (k - 1)) < n; ++k) {
		for (int i = 1, j = (1 << (k - 1)) + 1; j <= n; ++i, ++j) {
			if (lev[rmq[i][k - 1]] < lev[rmq[j][k - 1]]) {
				rmq[i][k] = rmq[i][k - 1]; }
			else {
				rmq[i][k] = rmq[j][k - 1]; } } } }

inline int lca(int x, int y) {
	x = pos[x]; y = pos[y]; 
	if (x > y) {
		swap(x, y); }
	int p = pwr[y - x + 1];
	return lev[rmq[x][p]] < lev[rmq[y - (1 << p) + 1][p]] ? 
		rmq[x][p] : rmq[y - (1 << p) + 1][p]; }

inline long long getDist(int x, int y) {
	return dst[x] + dst[y] - (dst[lca(x, y)] << 1); }

void getTree(int x, int f, int sz) {
	getCentroid(x, f, sz, x); getCentroid(x, f, sz, x); 
	par[x] = f; dp[x] = (1LL << 60); oki[x] = true;
	for (auto &ed : edg[x]) {
		int y = ed.first;
		if (!oki[y]) {
			getTree(y, x, szt[y]); } } }

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < n - 1; ++i) {
		int x = ++a[i], y = ++b[i], c = d[i];
		edg[x].push_back(make_pair(y, c));
		edg[y].push_back(make_pair(x, c)); }
	dfs(1, 0, 0); buildRmq((n << 1) - 1); getTree(1, 0, n); }

long long Query(int s, int a[], int t, int b[]) {
	long long ans = (1LL << 60);
	if (s > t) {
		swap(a, b); swap(s, t); }
	for (int i = 0; i < s; ++i) {
		for (int x = ++a[i]; x; x = par[x]) {
			dp[x] = min(dp[x], getDist(x, a[i])); } }
	for (int i = 0; i < t; ++i) {
		for (int x = ++b[i]; x; x = par[x]) {
			ans = min(ans, dp[x] + getDist(x, b[i])); } }
	for (int i = 0; i < s; ++i) {
		for (int x = a[i]; x; x = par[x]) {
			dp[x] = (1LL << 60); } }
	return ans; }

#ifdef HOME
int main(void) {
	freopen("factories.in", "r", stdin);
	freopen("factories.out", "w", stdout);
	int n, q; cin >> n >> q;
	int a[100], b[100], d[100];
	for (int i = 0; i < n - 1; ++i) {
		cin >> a[i] >> b[i] >> d[i]; }
	Init(n, a, b, d);
	while (q--) {
		int s, t; cin >> s >> t;
		for (int i = 0; i < s; ++i) {
			cin >> a[i]; }
		for (int i = 0; i < t; ++i) {
			cin >> b[i]; }
		cout << Query(s, a, t, b) << "\n"; }	
	return 0; }
#endif

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