oj.uz

Submission #993730

# Submission time Handle Problem Language Result Execution time Memory
993730 2024-06-06T10:40:55 Z zsombor Factories (JOI14_factories) C++17
15 / 100
 8000 ms 190656 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 <vector <int>> lift(6e5, vector<int>(20, 5e5));
vector <int> dep(6e5, 0);
vector <ll> dis(6e5, 0);

vector <bool> del(6e5, false);
vector <int> par(6e5, -1);
vector <ll> mn(6e5, 1e18);
queue <int> q;

void dfs(int x) {
	for (auto& p : g[x]) {
		ll y = p.first, w = p.second;
		if (lift[x][0] == y) continue;
		lift[y][0] = x;
		dep[y] = dep[x] + 1;
		dis[y] = dis[x] + w;
		dfs(y);
	}
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	for (int j = 19; j >= 0; j--) {
		if (dep[lift[a][j]] >= dep[b]) a = lift[a][j];
	}
	if (a == b) return a;
	for (int j = 19; j >= 0; j--) {
		if (lift[a][j] == lift[b][j]) continue;
		a = lift[a][j];
		b = lift[b][j];
	}
	return lift[a][0];
}

ll dist(int a, int b) {
	int c = lca(a, b);
	return dis[a] + dis[b] - 2 * dis[c];
}

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 cd(int x, int p) {
	if (del[x]) return;
	sz = get_C(x);
	get_C(x);
	int c = C;
	del[c] = true;
	par[c] = p;
	for (auto& p : g[c]) cd(p.first, c);
}

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] });
	}
	dfs(0);
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < n; i++) {
			lift[i][j] = lift[lift[i][j - 1]][j - 1];
		}
	}
	cd(0, -1);
}

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

ll ask(int x) {
	ll i = x, ret = 1e18;
	while (i > -1) {
		ret = min(ret, dist(x, i) + mn[i]);
		i = par[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 74 ms 115540 KB Output is correct
2 Correct 1506 ms 119904 KB Output is correct
3 Correct 2448 ms 119888 KB Output is correct
4 Correct 2375 ms 129444 KB Output is correct
5 Correct 2652 ms 129808 KB Output is correct
6 Correct 635 ms 129668 KB Output is correct
7 Correct 2582 ms 129360 KB Output is correct
8 Correct 2549 ms 129628 KB Output is correct
9 Correct 2630 ms 129872 KB Output is correct
10 Correct 547 ms 129240 KB Output is correct
11 Correct 2528 ms 129492 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 115536 KB Output is correct
2 Correct 2961 ms 157548 KB Output is correct
3 Correct 7577 ms 162568 KB Output is correct
4 Correct 909 ms 155060 KB Output is correct
5 Execution timed out 8061 ms 190656 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 115540 KB Output is correct
2 Correct 1506 ms 119904 KB Output is correct
3 Correct 2448 ms 119888 KB Output is correct
4 Correct 2375 ms 129444 KB Output is correct
5 Correct 2652 ms 129808 KB Output is correct
6 Correct 635 ms 129668 KB Output is correct
7 Correct 2582 ms 129360 KB Output is correct
8 Correct 2549 ms 129628 KB Output is correct
9 Correct 2630 ms 129872 KB Output is correct
10 Correct 547 ms 129240 KB Output is correct
11 Correct 2528 ms 129492 KB Output is correct
12 Correct 53 ms 115536 KB Output is correct
13 Correct 2961 ms 157548 KB Output is correct
14 Correct 7577 ms 162568 KB Output is correct
15 Correct 909 ms 155060 KB Output is correct
16 Execution timed out 8061 ms 190656 KB Time limit exceeded
17 Halted 0 ms 0 KB -