Submission #681218

#	Time	Username	Problem	Language	Result	Execution time	Memory
681218		SanguineChameleon	Factories (JOI14_factories)	C++17	100 / 100	3181 ms	175280 KiB

factories

#include "factories.h"

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

const int ms = 5e5 + 20;
const long long inf = 1e18L + 20;
const int st = 20;
vector<pair<int, int>> adj[ms];
vector<pair<int, long long>> vch[ms];
long long de[ms];
int ti[ms];
int to[ms];
int f[ms];
long long dp[ms][2];
int par[ms][st];
int tz;

void dfs1(int u, int pr) {
	ti[u] = ++tz;
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != pr) {
			par[v][0] = u;
			de[v] = de[u] + w;
			dfs1(v, u);
		}
	}
	to[u] = ++tz;
}

bool cmp(int u, int v) {
	return ti[u] < ti[v];
}

bool anc(int u, int v) {
	return ti[u] < ti[v] && to[v] < to[u];
}

int lca(int u, int v) {
	if (anc(u, v)) {
		return u;
	}
	if (anc(v, u)) {
		return v;
	}
	for (int i = st - 1; i >= 0; i--) {
		if (!anc(par[u][i], v)) {
			u = par[u][i];
		}
	}
	return par[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		int u = A[i];
		int v = B[i];
		u++;
		v++;
		int w = D[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (int i = 1; i <= N; i++) {
		f[i] = -1;
	}
	par[1][0] = 1;
	dfs1(1, -1);
	for (int k = 1; k < st; k++) {
		for (int i = 1; i <= N; i++) {
			par[i][k] = par[par[i][k - 1]][k - 1];
		}
	}
}

void dfs2(int u) {
	dp[u][0] = inf;
	dp[u][1] = inf;
	if (f[u] != -1) {
		dp[u][f[u]] = 0;
	}
	for (auto x: vch[u]) {
		int v = x.first;
		long long w = x.second;
		dfs2(v);
		dp[u][0] = min(dp[u][0], dp[v][0] + w);
		dp[u][1] = min(dp[u][1], dp[v][1] + w);
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> q;
	for (int i = 0; i < S; i++) {
		int u = X[i];
		u++;
		f[u] = 0;
		q.push_back(u);
	}
	for (int i = 0; i < T; i++) {
		int u = Y[i];
		u++;
		f[u] = 1;
		q.push_back(u);
	}
	int sz = q.size();
	sort(q.begin(), q.end(), cmp);
	for (int i = 0; i < sz - 1; i++) {
		q.push_back(lca(q[i], q[i + 1]));
	}
	sort(q.begin(), q.end(), cmp);
	q.erase(unique(q.begin(), q.end()), q.end());
	sz = q.size();
	int root = q[0];
	vector<int> p = {root};
	for (int i = 1; i < sz; i++) {
		int v = q[i];
		while (!anc(p.back(), v)) {
			p.pop_back();
		}
		int u = p.back();
		vch[u].push_back({v, de[v] - de[u]});
		p.push_back(v);
	}
	dfs2(root);
	long long res = inf;
	for (auto u: q) {
		res = min(res, dp[u][0] + dp[u][1]);
		vch[u].clear();
		f[u] = -1;
	}
	return res;
}

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