oj.uz

Submission #890089

# Submission time Handle Problem Language Result Execution time Memory
890089 2023-12-20T14:02:39 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 211120 KB 
#include <bits/stdc++.h>
#include <factories.h>
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long ans, spt[N][L], dis[N];
vector<pair<int, int>> adj[N];

void dfs(int v, int p) {
	for (auto [u, w]: adj[v])
		if (u != p) {
			par[u][0] = v;
			spt[u][0] = w;
			h[u] = h[v] + 1;
			dfs(u, v);
		}
}

void dfsu(int v, int p) {
	for (auto [u, w]: adj[v])
		if (u != p) {
			dfsu(u, v);
			dis[v] = min(dis[v], dis[u] + w);
		}
}

void dfsd(int v, int p) {
	for (auto [u, w]: adj[v])
		if (u != p) {
			dis[u] = min(dis[u], dis[v] + w);
			dfsd(u, v);
		}
}

long long distance(int v, int u) {
	long long res = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L && res < ans; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return res;

	for (int i = L - 1; i >= 0 && res < ans; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return res + spt[v][0] + spt[u][0];
}

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

	dfs(1, 0);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
			spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
		}
}

long long Query(int S, int X[], int T, int Y[]) {
	ans = I;
	if (S < Q) {
		for (int i = 0; i < T; i++)
			for (int j = 0; j < S; j++)
				ans = min(ans, distance(Y[i] + 1, X[j] + 1));
		return ans;
	}
	
	for (int i = 0; i < N; dis[i++] = I);
	for (int i = 0; i < S; dis[X[i++] + 1] = 0); 
	dfsu(1, 0);
	dfsd(1, 0);

	for (int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i] + 1]);
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35416 KB Output is correct
2 Correct 714 ms 41864 KB Output is correct
3 Correct 2024 ms 41868 KB Output is correct
4 Correct 388 ms 42116 KB Output is correct
5 Correct 798 ms 42172 KB Output is correct
6 Correct 1022 ms 41868 KB Output is correct
7 Correct 2017 ms 41872 KB Output is correct
8 Correct 1705 ms 41880 KB Output is correct
9 Correct 787 ms 42168 KB Output is correct
10 Correct 947 ms 41876 KB Output is correct
11 Correct 1958 ms 41880 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1250 ms 187156 KB Output is correct
3 Correct 2363 ms 189824 KB Output is correct
4 Correct 851 ms 187704 KB Output is correct
5 Correct 3170 ms 211120 KB Output is correct
6 Correct 2048 ms 190176 KB Output is correct
7 Correct 2062 ms 69240 KB Output is correct
8 Correct 1012 ms 69372 KB Output is correct
9 Correct 3037 ms 72016 KB Output is correct
10 Correct 1603 ms 70068 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35416 KB Output is correct
2 Correct 714 ms 41864 KB Output is correct
3 Correct 2024 ms 41868 KB Output is correct
4 Correct 388 ms 42116 KB Output is correct
5 Correct 798 ms 42172 KB Output is correct
6 Correct 1022 ms 41868 KB Output is correct
7 Correct 2017 ms 41872 KB Output is correct
8 Correct 1705 ms 41880 KB Output is correct
9 Correct 787 ms 42168 KB Output is correct
10 Correct 947 ms 41876 KB Output is correct
11 Correct 1958 ms 41880 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1250 ms 187156 KB Output is correct
14 Correct 2363 ms 189824 KB Output is correct
15 Correct 851 ms 187704 KB Output is correct
16 Correct 3170 ms 211120 KB Output is correct
17 Correct 2048 ms 190176 KB Output is correct
18 Correct 2062 ms 69240 KB Output is correct
19 Correct 1012 ms 69372 KB Output is correct
20 Correct 3037 ms 72016 KB Output is correct
21 Correct 1603 ms 70068 KB Output is correct
22 Correct 6067 ms 188440 KB Output is correct
23 Correct 3785 ms 189460 KB Output is correct
24 Correct 7616 ms 191048 KB Output is correct
25 Correct 7218 ms 193056 KB Output is correct
26 Execution timed out 8019 ms 191580 KB Time limit exceeded
27 Halted 0 ms 0 KB -