Submission #921893

#	Time	Username	Problem	Language	Result	Execution time	Memory
921893		falaz	Factories (JOI14_factories)	C++17	100 / 100	3519 ms	291448 KiB

factories

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

const int M = 5e5 + 1;
int st[M], fn[M], t, cnt, n , loc[M], ql, qr , TV = 1, lg[2 * M];
vector<pair<int, long long>> adj[M];
long long dis[M], seg[2][M << 2];
pair<int, int> par[20][M << 1];

void dfs(int v, int p, long long d1, int h) {
	dis[v] = d1;
	st[v] = t++;
	loc[v] = cnt;
	par[0][cnt++] = {h, v};
	for (auto u : adj[v]) 
		if (u.first != p) { 
			dfs(u.first, v, d1 + 1ll * u.second, h + 1);
			par[0][cnt++] = {h, v};
		}
	fn[v] = t - 1;
	return;
}

void update(int i, long long k, bool g) {
	i = i + TV;
	seg[g][i] = k;
	i /= 2;
	while (i) {
		seg[g][i] = min(seg[g][i << 1], seg[g][i << 1 | 1]);
		i /= 2;
	}
}

long long get(bool g) {
	ql = ql + TV;
	qr = qr + 1 + TV;
	long long ret = 1e18;
	while (ql < qr) {
		if (ql & 1)
			ret = min(ret, seg[g][ql++]);
		if (qr & 1)
			ret = min(ret, seg[g][--qr]);
		ql /= 2;
		qr /= 2;
	}
	return ret;
}

void rem(int i, bool g) {
	i = i + TV;
	seg[g][i] = 1e18;
	i /= 2;
	while (i) {
		seg[g][i] = 1e18;
		i /= 2;
	}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0, 0, 0);
	for (int i = 2; i < 2 * n; i++)
		lg[i] = lg[i / 2] + 1;
	while (TV < N)
		TV *= 2;
	for (int i = 0; i < 2 * TV; i++)
		seg[0][i] = seg[1][i] = 1e18;
	for (int i = 1; i < 20; i++) 
		for (int j = 0; j + (1 << i) < 2 * n; j++) 
			par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pair<int, int>> sv;
	for (int i = 0; i < S; i++) {
		update(st[X[i]], dis[X[i]], 0);
		sv.push_back({st[X[i]], X[i]});
	}
	for (int i = 0; i < T; i++) {
		update(st[Y[i]], dis[Y[i]], 1);
		sv.push_back({st[Y[i]], Y[i]});
	}
	sort(sv.begin(), sv.end());
	long long ans = 1e18 ;
	for (int i = 0; i < int(sv.size()); i++) {
		int v = sv[i].second;
		ql = st[v];
		qr = fn[v];
		long long f = get(0);
		ql = st[v];
		qr = fn[v];
		f += get(1);
		f -= (2ll * dis[v]);
		ans = min(ans, f);
		if (i < int(sv.size()) - 1) {
			int vv = sv[i].second, uu = sv[i + 1].second;
			if (loc[vv] > loc[uu])
				swap(vv, uu);
			int SV = loc[vv], SU = loc[uu], LG = lg[SU - SV + 1];
			pair<int, int> lca = min(par[LG][SV], par[LG][SU - (1 << LG) + 1]);
			v = lca.second;
			ql = st[v];
			qr = fn[v];
			f = get(0);
			ql = st[v];
			qr = fn[v];
			f += get(1);
			f -= (2ll * dis[v]);
	 		ans = min(ans, f);
		}
	}
	for (int i = 0; i < S; i++) 
		rem(st[X[i]], 0);
	for (int i = 0; i < T; i++)
		rem(st[Y[i]], 1);
	return ans;
}

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