Submission #33040

#	Time	Username	Problem	Language	Result	Execution time	Memory
33040		aome	Factories (JOI14_factories)	C++14	15 / 100	6000 ms	127352 KiB

factories

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

const int N = 500005;
const long long INF = 1e18;

typedef pair<int, int> ii;

int n, h[N];
int cnt, st[N];
int par[20][N];
long long res;
long long dis[N];
long long f[2][N];
bool flag[2][N];
vector<ii> G[N];

void dfs(int u) {
	st[u] = cnt++;
	for (auto v : G[u]) {
		if (par[0][u] == v.first) continue;
		par[0][v.first] = u, dis[v.first] = dis[u] + v.second;
		h[v.first] = h[u] + 1, dfs(v.first);
	}
}

int lca(int u, int v) {
	if (h[u] > h[v]) swap(u, v);
	for (int i = 18; i >= 0; --i) {
		if (h[par[i][v]] >= h[u]) v = par[i][v];
	}
	for (int i = 18; i >= 0; --i) {
		if (par[i][v] != par[i][u]) {
			v = par[i][v], u = par[i][u];
		}
	}
	return (u == v) ? u : par[0][u];
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 0; i < (n - 1); ++i) {
		G[a[i]].push_back(ii(b[i], d[i]));
		G[b[i]].push_back(ii(a[i], d[i]));
	}
	dfs(0);
	for (int i = 1; i <= 18; ++i) {
		for (int j = 1; j <= n; ++j) {
			par[i][j] = par[i - 1][par[i - 1][j]];
		}
	}
}

vector<int> nG[N];

void solve(int u) {
	for (int i = 0; i < 2; ++i) {
		if (flag[i][u]) f[i][u] = min(f[i][u], dis[u]);
	}
	for (auto v : nG[u]) {
		solve(v);
		for (int i = 0; i < 2; ++i) f[i][u] = min(f[i][u], f[i][v]);
	}
	long long mn[2];
	mn[0] = mn[1] = INF;
	for (auto v : nG[u]) {
		for (int i = 0; i < 2; ++i) {
			res = min(res, f[i][v] + mn[i ^ 1] - 2 * dis[u]);
		}
		for (int i = 0; i < 2; ++i) {
			mn[i] = min(mn[i], f[i][v]);
		}
	}
	for (int i = 0; i < 2; ++i) {
		if (flag[i ^ 1][u]) res = min(res, mn[i] - dis[u]);
	}
}

long long Query(int s, int x[], int t, int y[]) {
	vector<int> ver;
	for (int i = 0; i < s; ++i) ver.push_back(x[i]), flag[0][x[i]] = 1;
	for (int i = 0; i < t; ++i) ver.push_back(y[i]), flag[1][y[i]] = 1;
	sort(ver.begin(), ver.end(), [&](int x, int y) {
		return st[x] < st[y];
	});
	int sz = ver.size();
	for (int i = 1; i < sz; ++i) {
		ver.push_back(lca(ver[i - 1], ver[i]));
	}
	sort(ver.begin(), ver.end(), [&](int x, int y) {
		return st[x] < st[y];
	});
	ver.erase(unique(ver.begin(), ver.end()), ver.end());
	sz = ver.size();
	for (int i = 1; i < sz; ++i) {
		int p = lca(ver[i - 1], ver[i]);
		nG[p].push_back(ver[i]);
		// cout << p << ' ' << ver[i] << '\n';
	}
	for (int i = 0; i < sz; ++i) {
		f[0][ver[i]] = f[1][ver[i]] = INF;
	}
	res = INF, solve(ver[0]);
	for (int i = 0; i < sz; ++i) {
		flag[0][ver[i]] = flag[1][ver[i]] = 0;
		nG[ver[i]].clear();
	}
	return res;
}

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