Submission #34313

#	Time	Username	Problem	Language	Result	Execution time	Memory
34313		aome	Factories (JOI14_factories)	C++14	100 / 100	4586 ms	277440 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, TIME;
int P[N], E[N * 2], H[N], LG[N * 2];
ii rmq[20][N * 2];
long long res;
long long dis[N];
long long f[2][N];
bool color[2][N];
vector<ii> G[N];

void dfs(int u, int p) {
	P[u] = ++TIME, E[TIME] = u;
	for (auto v : G[u]) {
		if (v.first == p) continue;
		dis[v.first] = dis[u] + v.second;
		H[v.first] = H[u] + 1, dfs(v.first, u);
		E[++TIME] = u;
	}
}

ii get(int l, int r) {
	int k = LG[r - l + 1];
	return min(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}

int lca(int u, int v) {
	if (P[u] > P[v]) swap(u, v);
	return get(P[u], P[v]).second;
}

void Init(int n, int a[], int b[], int d[]) {
	for (int i = 2; i <= n * 2; ++i) LG[i] = LG[i >> 1] + 1;
	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, 0);
	for (int i = 1; i <= TIME; ++i) {
		rmq[0][i].first = H[E[i]];
		rmq[0][i].second = E[i];
	}
	for (int i = 1; i < 20; ++i) {
		for (int j = 1; j + (1 << i) - 1 <= TIME; ++j) {
			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
		} 
	}
}

vector<int> nG[N];

void solve(int u) {
	for (int i = 0; i < 2; ++i) {
		if (color[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 (color[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]), color[0][x[i]] = 1;
	for (int i = 0; i < t; ++i) ver.push_back(y[i]), color[1][y[i]] = 1;
	sort(ver.begin(), ver.end(), [&](int x, int y) {
		return P[x] < P[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 P[x] < P[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) {
		color[0][ver[i]] = color[1][ver[i]] = 0;
		nG[ver[i]].clear();
	}
	return res;
}

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