Submission #88116

#	Time	Username	Problem	Language	Result	Execution time	Memory
88116		KCSC	Factories (JOI14_factories)	C++14	15 / 100	8055 ms	229484 KiB

factories

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

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

const int LOG = 19;
const int DIM = 500005;

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

void dfs(int x, int f, int d) {
	dst[x] = dst[f] + d; 
	anc[x][0] = f; lev[x] = lev[f] + 1;
	for (int i = 1; i < LOG; ++i) {
		anc[x][i] = anc[anc[x][i - 1]][i - 1]; }
	for (auto &ed : edg[x]) {
		int y = ed.first, c = ed.second;
		if (y != f) {
			dfs(y, x, c); } } } 

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; } }

int lca(int x, int y) {
	if (lev[x] > lev[y]) {	
		swap(x, y); }
	for (int i = LOG - 1; i >= 0; --i) {
		if (lev[y] - (1 << i) >= lev[x]) {
			y = anc[y][i]; } }
	for (int i = LOG - 1; i >= 0; --i) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i]; y = anc[y][i]; } }
	if (x == y) {
		return x; }
	else {
		return anc[x][0]; } }

long long getDist(int x, int y) {
	return dst[x] + dst[y] - dst[lca(x, y)] * 2; }

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); getTree(1, 0, n); }

long long Query(int s, int a[], int t, int b[]) {
	long long ans = (1LL << 60);
	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: 0 / 18
• Subtask 3: 0 / 67