Submission #921644

#	Time	Username	Problem	Language	Result	Execution time	Memory
921644		vjudge1	Factories (JOI14_factories)	C++17	15 / 100	8041 ms	199408 KiB

factories

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

long long st[500001], fn[500001], dis[500001], par[20][500001], t = 0, n, seg[2000001][2], h[500001], ans;
vector<pair<int, long long>> adj[500001];

void dfs( long long v, long long p, long long d1, long long h1) {
	dis[v] = d1;
	h[v] = h1;
	st[v] = t++;
	par[0][v] = p;
	for ( long long i = 1; i < 20; i++) 
		par[i][v] = par[i - 1][par[i - 1][v]];
	for (auto u : adj[v]) 
		if (u.first != p) 
			dfs(u.first, v, d1 + 1ll * u.second, h1 + 1);
	fn[v] = t - 1;
//	cout << v << " " << st[v] << " " << fn[v] << endl;
	return;
}

long long getp(long long v, long long k) {
	for (long long i = 20 - 1; ~i; i--)
		if ((k >> i) & 1)
			v = par[i][v];
	return v;
}

long long lca(long long v, long long u) {
	if (h[v] < h[u])
		swap(v, u);
	v = getp(v, h[v] - h[u]);
	if (v == u)
		return v;
	for (long long i = 20 - 1 ; ~i; i--) 
		if (par[i][v] != par[i][u]) {
			v = par[i][v];
			u = par[i][u];
		}
	return par[0][v];
}

void update(int v, int l, int r, long long i, long long k, bool g) {
//	cout << v << "A" << endl;
	if (l == r) {
		seg[v][g] = k;
		return;
	}
	long long mid = (r + l) / 2;
	(i <= mid) ? update(v * 2, l, mid, i, k, g) : update(v * 2 + 1, mid + 1, r, i, k, g);
	seg[v][g] = min(seg[v * 2][g], seg[v * 2 + 1][g]);
}

long long get(int v, int l, int r, long long ql, long long qr, bool g) {
//	cout << "a" << seg[v][g] << " " << l << " " << r << " " << ql << " " << qr << endl;
	if (ql <= l && r <= qr) 
		return seg[v][g];
	if (r < ql || qr < l) 
		return 1e18 ;
	long long mid = (r + l) / 2;
	return min(get(v * 2, l, mid, ql, qr, g), get(v * 2 + 1, mid + 1, r, ql, qr, g));
}

void rem(int v, int l, int r, long long i, bool g) {
//	cout << v << "C" << endl;
	seg[v][g] = 1e18 ;
	if (l == r) 
		return;
	long long mid = (r + l) / 2;
	(i <= mid) ? rem(v * 2, l, mid, i, g) : rem(v * 2 + 1, mid + 1, r, i, g);

}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (long long 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);
	queue<pair<int, pair<int, int>>> q;
	q.push({1, {0, n - 1}});
	while (q.size()) {
		int v = q.front().first, l = q.front().second.first, r = q.front().second.second;
		seg[v][0] = seg[v][1] = 1e18 ;
		q.pop();
//		cout << v << endl;
		if (l != r) {
			int mid = (l + r) / 2;
			q.push({v * 2, {l, mid}});
			q.push({v * 2 + 1, {mid + 1, r}});
		}
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<pair<int, int>> sv;
	for (long long i = 0; i < S; i++) {
		update(1, 0, n - 1, st[X[i]], dis[X[i]], 0);
		sv.push_back({st[X[i]], X[i]});
	}
	for (long long i = 0; i < T; i++) {
		update(1, 0, n - 1, st[Y[i]], dis[Y[i]], 1);
		sv.push_back({st[Y[i]], Y[i]});
	}
	sort(sv.begin(), sv.end());
	ans = 1e18 ;
	for (long long i = 0; i < int32_t(sv.size()); i++) {
		long long v = sv[i].second;
		long long f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2ll * dis[v]);
//		cout << f << endl;
//		cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
		ans = min(ans, f);
		if (i < int32_t(sv.size()) - 1) {
			v = lca(sv[i].second, sv[i + 1].second);
			f = get(1, 0, n - 1, st[v], fn[v], 0) + get(1, 0, n - 1, st[v], fn[v], 1) - (2ll * dis[v]);
	 		ans = min(ans, f);
//			cout << f << endl;
//			cout << get(1, 0, n - 1, st[v], fn[v], 0) << " " << get(1, 0, n - 1, st[v], fn[v], 1) << endl;
//			cout << v<< endl;
		}
	}
	for (long long i = 0; i < S; i++) 
		rem(1, 0, n - 1, st[X[i]], 0);
	for (long long i = 0; i < T; i++)
		rem(1, 0, n - 1, st[Y[i]], 1);
	return ans;
}

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