oj.uz

Submission #921894

# Submission time Handle Problem Language Result Execution time Memory
921894 2024-02-04T13:03:45 Z falaz Factories (JOI14_factories) C++17
100 / 100
 5819 ms 293220 KB 
//#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, 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 v, int l, int r, int i, long long k, bool g) {
	if (l == r) {
		seg[g][v] = k;
		return;
	}
	int mid = (r + l) >> 1;
	if (i <= mid) {
		if (l == mid) 
			seg[g][v << 1] = k;
		else
			update(v << 1, l, mid, i, k, g);
	}
	else {
		if (mid + 1 == r) 
			seg[g][v << 1 | 1] = k;
		else
			update(v << 1 | 1, mid + 1, r, i, k, g);
	}
	seg[g][v] = min(seg[g][v << 1], seg[g][v << 1 | 1]);
}

long long get(int v, int l, int r, bool g) {
	if (ql <= l && r <= qr) 
		return seg[g][v];
	if (r < ql || qr < l) 
		return 1e18 ;
	int mid = (r + l) >> 1;
	long long a = 1e18, b = 1e18; 
	if (ql <= l && mid <= qr) 
		a = seg[g][v << 1];
	else if (mid < ql || qr < l)
		a = a;
	else
		a = get(v << 1, l, mid, g);
	if (ql <= mid + 1 && r <= qr)
		b = seg[g][v << 1 | 1];
	else if (r < ql || qr < mid + 1)
		b = b;
	else
		b = get(v << 1 | 1, mid + 1, r, g);
	return min(a, b);
}

void rem(int v, int l, int r, int i, bool g) {
	seg[g][v] = 1e18 ;
	if (l == r) 
		return;
	int mid = (r + l) >> 1;
	if (i <= mid) {
		if (l == mid) {
			seg[g][v << 1] = 1e18;
			return;
		}
		rem(v << 1, l, mid, i, g);
	}
	else {
		if (mid + 1 == r) {
			seg[g][v << 1 | 1] = 1e18;
			return;
		}
		rem(v << 1 | 1,  mid + 1, r, i, g);
	}
}

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;
	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[0][v] = seg[1][v] = 1e18;
		q.pop();
		if (l != r) {
			int mid = (l + r) >> 1;
			q.push({v << 1, {l, mid}});
			q.push({v << 1 | 1, {mid + 1, r}});
		}
	}
	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(1, 0, n - 1, st[X[i]], dis[X[i]], 0);
		sv.push_back({st[X[i]], X[i]});
	}
	for (int 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());
	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(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (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(1, 0, n - 1, 0) + get(1, 0, n - 1, 1) - (2ll * dis[v]);
	 		ans = min(ans, f);
		}
	}
	for (int i = 0; i < S; i++) 
		rem(1, 0, n - 1, st[X[i]], 0);
	for (int 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 39 ms 63976 KB Output is correct
2 Correct 1481 ms 76740 KB Output is correct
3 Correct 1628 ms 76772 KB Output is correct
4 Correct 1584 ms 76624 KB Output is correct
5 Correct 1599 ms 77200 KB Output is correct
6 Correct 1215 ms 76748 KB Output is correct
7 Correct 1672 ms 76780 KB Output is correct
8 Correct 1627 ms 76856 KB Output is correct
9 Correct 1673 ms 77276 KB Output is correct
10 Correct 1205 ms 76760 KB Output is correct
11 Correct 1673 ms 76784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 64088 KB Output is correct
2 Correct 2816 ms 252156 KB Output is correct
3 Correct 3079 ms 258100 KB Output is correct
4 Correct 2440 ms 254004 KB Output is correct
5 Correct 2577 ms 293220 KB Output is correct
6 Correct 3387 ms 257916 KB Output is correct
7 Correct 2861 ms 124920 KB Output is correct
8 Correct 2082 ms 123888 KB Output is correct
9 Correct 2381 ms 129200 KB Output is correct
10 Correct 2909 ms 125200 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 63976 KB Output is correct
2 Correct 1481 ms 76740 KB Output is correct
3 Correct 1628 ms 76772 KB Output is correct
4 Correct 1584 ms 76624 KB Output is correct
5 Correct 1599 ms 77200 KB Output is correct
6 Correct 1215 ms 76748 KB Output is correct
7 Correct 1672 ms 76780 KB Output is correct
8 Correct 1627 ms 76856 KB Output is correct
9 Correct 1673 ms 77276 KB Output is correct
10 Correct 1205 ms 76760 KB Output is correct
11 Correct 1673 ms 76784 KB Output is correct
12 Correct 14 ms 64088 KB Output is correct
13 Correct 2816 ms 252156 KB Output is correct
14 Correct 3079 ms 258100 KB Output is correct
15 Correct 2440 ms 254004 KB Output is correct
16 Correct 2577 ms 293220 KB Output is correct
17 Correct 3387 ms 257916 KB Output is correct
18 Correct 2861 ms 124920 KB Output is correct
19 Correct 2082 ms 123888 KB Output is correct
20 Correct 2381 ms 129200 KB Output is correct
21 Correct 2909 ms 125200 KB Output is correct
22 Correct 4311 ms 251648 KB Output is correct
23 Correct 4496 ms 252928 KB Output is correct
24 Correct 4658 ms 256604 KB Output is correct
25 Correct 4695 ms 258788 KB Output is correct
26 Correct 5420 ms 256720 KB Output is correct
27 Correct 4371 ms 285840 KB Output is correct
28 Correct 3690 ms 253780 KB Output is correct
29 Correct 5819 ms 256156 KB Output is correct
30 Correct 5518 ms 255380 KB Output is correct
31 Correct 5476 ms 256444 KB Output is correct
32 Correct 2223 ms 131484 KB Output is correct
33 Correct 1819 ms 125112 KB Output is correct
34 Correct 2444 ms 123212 KB Output is correct
35 Correct 2509 ms 123236 KB Output is correct
36 Correct 2594 ms 124312 KB Output is correct
37 Correct 2747 ms 124252 KB Output is correct