oj.uz

Submission #921890

# Submission time Handle Problem Language Result Execution time Memory
921890 2024-02-04T12:56:34 Z falaz Factories (JOI14_factories) C++17
100 / 100
 3687 ms 310192 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 , 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;
//	cout << "A" <<  i << " " << k << " " << g << endl;
	seg[g][i] = k;
	i /= 2;
	while (i) {
//		cout << i << " ";
		seg[g][i] = min(seg[g][i << 1], seg[g][i << 1 | 1]);
//		cout << seg[g][i] << endl;
		i /= 2;
	}
//	cout << endl;
}

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

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

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 = 0; i < n; i++)
//		cout << i << " " << st[i] << " " << fn[i] << endl;
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64088 KB Output is correct
2 Correct 557 ms 86100 KB Output is correct
3 Correct 697 ms 86352 KB Output is correct
4 Correct 645 ms 86352 KB Output is correct
5 Correct 793 ms 86640 KB Output is correct
6 Correct 530 ms 86180 KB Output is correct
7 Correct 674 ms 86092 KB Output is correct
8 Correct 637 ms 86292 KB Output is correct
9 Correct 810 ms 86640 KB Output is correct
10 Correct 545 ms 86180 KB Output is correct
11 Correct 688 ms 86196 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 64088 KB Output is correct
2 Correct 1613 ms 268824 KB Output is correct
3 Correct 1857 ms 274432 KB Output is correct
4 Correct 1279 ms 266244 KB Output is correct
5 Correct 2015 ms 310192 KB Output is correct
6 Correct 2099 ms 275012 KB Output is correct
7 Correct 1298 ms 138320 KB Output is correct
8 Correct 917 ms 136976 KB Output is correct
9 Correct 1290 ms 142904 KB Output is correct
10 Correct 1285 ms 138776 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64088 KB Output is correct
2 Correct 557 ms 86100 KB Output is correct
3 Correct 697 ms 86352 KB Output is correct
4 Correct 645 ms 86352 KB Output is correct
5 Correct 793 ms 86640 KB Output is correct
6 Correct 530 ms 86180 KB Output is correct
7 Correct 674 ms 86092 KB Output is correct
8 Correct 637 ms 86292 KB Output is correct
9 Correct 810 ms 86640 KB Output is correct
10 Correct 545 ms 86180 KB Output is correct
11 Correct 688 ms 86196 KB Output is correct
12 Correct 13 ms 64088 KB Output is correct
13 Correct 1613 ms 268824 KB Output is correct
14 Correct 1857 ms 274432 KB Output is correct
15 Correct 1279 ms 266244 KB Output is correct
16 Correct 2015 ms 310192 KB Output is correct
17 Correct 2099 ms 275012 KB Output is correct
18 Correct 1298 ms 138320 KB Output is correct
19 Correct 917 ms 136976 KB Output is correct
20 Correct 1290 ms 142904 KB Output is correct
21 Correct 1285 ms 138776 KB Output is correct
22 Correct 2720 ms 275516 KB Output is correct
23 Correct 2510 ms 275960 KB Output is correct
24 Correct 2888 ms 280568 KB Output is correct
25 Correct 3048 ms 281708 KB Output is correct
26 Correct 3170 ms 279224 KB Output is correct
27 Correct 3019 ms 308052 KB Output is correct
28 Correct 2119 ms 274404 KB Output is correct
29 Correct 3469 ms 278740 KB Output is correct
30 Correct 3687 ms 277788 KB Output is correct
31 Correct 3273 ms 278732 KB Output is correct
32 Correct 1142 ms 144408 KB Output is correct
33 Correct 858 ms 138248 KB Output is correct
34 Correct 1088 ms 136284 KB Output is correct
35 Correct 983 ms 136276 KB Output is correct
36 Correct 1264 ms 137316 KB Output is correct
37 Correct 1184 ms 137300 KB Output is correct