oj.uz

Submission #993793

# Submission time Handle Problem Language Result Execution time Memory
993793 2024-06-06T12:32:22 Z zsombor Factories (JOI14_factories) C++17
100 / 100
 3097 ms 253616 KB 
#include "factories.h"
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

int n, sz, C;
vector <vector <pair <int, ll>>> g(6e5);
vector <bool> del(6e5, false);
vector <int> par(6e5, -1);
vector <int> dep(6e5, 0);
vector <vector <ll>> dis(6e5, vector <ll>(20, 1e18));
vector <ll> mn(6e5, 1e18);
queue <int> q;

int get_C(int x) {
	if (del[x]) return 0;
	del[x] = true;
	int mx = 0, sum = 1;
	for (auto& p : g[x]) {
		int y = p.first, cur;
		cur = get_C(y);
		mx = max(mx, cur);
		sum += cur;
	}
	mx = max(mx, sz - sum);
	if (mx <= sz / 2) C = x;
	del[x] = false;
	return sum;
}

void dfs(int x, ll d, vector <pair <int, ll>>& v) {
	if (del[x]) return;
	del[x] = true;
	v.push_back({ x,d });
	for (auto p : g[x]) dfs(p.first, d + p.second, v);
	del[x] = false;
}

void cd(int x, int p, int d) {
	if (del[x]) return;
	sz = get_C(x);
	get_C(x);
	int c = C;
	vector <pair <int, ll>> v;
	dfs(c, 0, v);
	del[c] = true;
	par[c] = p;
	dep[c] = d;
	for (auto& p : g[c]) cd(p.first, c, d + 1);
	for (auto& p : v) dis[p.first][dep[c]] = p.second;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		g[A[i]].push_back({ B[i],D[i] });
		g[B[i]].push_back({ A[i],D[i] });
	}
	cd(0, -1, 0);
}

void add(int x) {
	for (int i = x; i > -1; i = par[i]) {
		mn[i] = min(mn[i], dis[x][dep[i]]);
		q.push(i);
	}
}

ll ask(int x) {
	ll ret = 1e18;
	for (int i = x; i > -1; i = par[i]) ret = min(ret, dis[x][dep[i]] + mn[i]);
	return ret;
}

ll Query(int S, int X[], int T, int Y[]) {
	ll ans = 1e18;
	for (int i = 0; i < T; i++) add(Y[i]);
	for (int i = 0; i < S; i++) ans = min(ans, ask(X[i]));
	while (q.size()) { mn[q.front()] = 1e18; q.pop(); }
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 157816 KB Output is correct
2 Correct 325 ms 162308 KB Output is correct
3 Correct 333 ms 162308 KB Output is correct
4 Correct 317 ms 162348 KB Output is correct
5 Correct 358 ms 162560 KB Output is correct
6 Correct 222 ms 162352 KB Output is correct
7 Correct 330 ms 162420 KB Output is correct
8 Correct 304 ms 162308 KB Output is correct
9 Correct 359 ms 162600 KB Output is correct
10 Correct 218 ms 162264 KB Output is correct
11 Correct 305 ms 162308 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 157776 KB Output is correct
2 Correct 1625 ms 200528 KB Output is correct
3 Correct 2216 ms 224232 KB Output is correct
4 Correct 590 ms 214196 KB Output is correct
5 Correct 2710 ms 253616 KB Output is correct
6 Correct 2251 ms 224700 KB Output is correct
7 Correct 722 ms 182576 KB Output is correct
8 Correct 339 ms 181796 KB Output is correct
9 Correct 854 ms 187268 KB Output is correct
10 Correct 745 ms 183372 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 157816 KB Output is correct
2 Correct 325 ms 162308 KB Output is correct
3 Correct 333 ms 162308 KB Output is correct
4 Correct 317 ms 162348 KB Output is correct
5 Correct 358 ms 162560 KB Output is correct
6 Correct 222 ms 162352 KB Output is correct
7 Correct 330 ms 162420 KB Output is correct
8 Correct 304 ms 162308 KB Output is correct
9 Correct 359 ms 162600 KB Output is correct
10 Correct 218 ms 162264 KB Output is correct
11 Correct 305 ms 162308 KB Output is correct
12 Correct 70 ms 157776 KB Output is correct
13 Correct 1625 ms 200528 KB Output is correct
14 Correct 2216 ms 224232 KB Output is correct
15 Correct 590 ms 214196 KB Output is correct
16 Correct 2710 ms 253616 KB Output is correct
17 Correct 2251 ms 224700 KB Output is correct
18 Correct 722 ms 182576 KB Output is correct
19 Correct 339 ms 181796 KB Output is correct
20 Correct 854 ms 187268 KB Output is correct
21 Correct 745 ms 183372 KB Output is correct
22 Correct 1754 ms 224268 KB Output is correct
23 Correct 1727 ms 225644 KB Output is correct
24 Correct 2538 ms 229404 KB Output is correct
25 Correct 2527 ms 230260 KB Output is correct
26 Correct 2611 ms 229596 KB Output is correct
27 Correct 3097 ms 246756 KB Output is correct
28 Correct 675 ms 215564 KB Output is correct
29 Correct 2526 ms 223968 KB Output is correct
30 Correct 2654 ms 223092 KB Output is correct
31 Correct 2655 ms 217864 KB Output is correct
32 Correct 860 ms 183716 KB Output is correct
33 Correct 335 ms 175136 KB Output is correct
34 Correct 554 ms 174672 KB Output is correct
35 Correct 530 ms 174304 KB Output is correct
36 Correct 744 ms 174976 KB Output is correct
37 Correct 703 ms 175056 KB Output is correct