oj.uz

Submission #921644

# Submission time Handle Problem Language Result Execution time Memory
921644 2024-02-04T08:42:20 Z vjudge1 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 199408 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 82896 KB Output is correct
2 Correct 1964 ms 94488 KB Output is correct
3 Correct 2269 ms 94528 KB Output is correct
4 Correct 2063 ms 94684 KB Output is correct
5 Correct 1833 ms 94804 KB Output is correct
6 Correct 1779 ms 94496 KB Output is correct
7 Correct 2257 ms 94528 KB Output is correct
8 Correct 2131 ms 94580 KB Output is correct
9 Correct 1889 ms 94812 KB Output is correct
10 Correct 1783 ms 94492 KB Output is correct
11 Correct 2261 ms 94528 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 80476 KB Output is correct
2 Correct 6713 ms 195548 KB Output is correct
3 Execution timed out 8041 ms 199408 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 82896 KB Output is correct
2 Correct 1964 ms 94488 KB Output is correct
3 Correct 2269 ms 94528 KB Output is correct
4 Correct 2063 ms 94684 KB Output is correct
5 Correct 1833 ms 94804 KB Output is correct
6 Correct 1779 ms 94496 KB Output is correct
7 Correct 2257 ms 94528 KB Output is correct
8 Correct 2131 ms 94580 KB Output is correct
9 Correct 1889 ms 94812 KB Output is correct
10 Correct 1783 ms 94492 KB Output is correct
11 Correct 2261 ms 94528 KB Output is correct
12 Correct 18 ms 80476 KB Output is correct
13 Correct 6713 ms 195548 KB Output is correct
14 Execution timed out 8041 ms 199408 KB Time limit exceeded
15 Halted 0 ms 0 KB -