oj.uz

Submission #889238

# Submission time Handle Problem Language Result Execution time Memory
889238 2023-12-19T08:32:22 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 213336 KB 
#include <bits/stdc++.h>
#include <factories.h>
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 60;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long 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 ans = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L; i++)
		if ((1 << i) & (h[v] - h[u])) {
			ans += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return ans;

	for (int i = L - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			ans += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return ans + 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];
		}
	for (int i = 0; i < N; dis[i++] = I);
}

long long Query(int S, int X[], int T, int Y[]) {
	if (S < Q) {
		long long ans = I;
		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 < S; i++) 
		dis[X[i] + 1] = 0;
	dfsu(1, 0);
	dfsd(1, 0);

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37560 KB Output is correct
2 Correct 651 ms 42068 KB Output is correct
3 Correct 1995 ms 41872 KB Output is correct
4 Correct 543 ms 41864 KB Output is correct
5 Correct 809 ms 42068 KB Output is correct
6 Correct 459 ms 42064 KB Output is correct
7 Correct 2051 ms 41880 KB Output is correct
8 Correct 1684 ms 41888 KB Output is correct
9 Correct 753 ms 42324 KB Output is correct
10 Correct 492 ms 42068 KB Output is correct
11 Correct 1941 ms 41876 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 1211 ms 189232 KB Output is correct
3 Correct 3248 ms 191876 KB Output is correct
4 Correct 798 ms 189860 KB Output is correct
5 Correct 3584 ms 213336 KB Output is correct
6 Correct 2619 ms 191980 KB Output is correct
7 Correct 4619 ms 71484 KB Output is correct
8 Correct 935 ms 71356 KB Output is correct
9 Correct 5182 ms 74068 KB Output is correct
10 Correct 2707 ms 71892 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 37560 KB Output is correct
2 Correct 651 ms 42068 KB Output is correct
3 Correct 1995 ms 41872 KB Output is correct
4 Correct 543 ms 41864 KB Output is correct
5 Correct 809 ms 42068 KB Output is correct
6 Correct 459 ms 42064 KB Output is correct
7 Correct 2051 ms 41880 KB Output is correct
8 Correct 1684 ms 41888 KB Output is correct
9 Correct 753 ms 42324 KB Output is correct
10 Correct 492 ms 42068 KB Output is correct
11 Correct 1941 ms 41876 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 1211 ms 189232 KB Output is correct
14 Correct 3248 ms 191876 KB Output is correct
15 Correct 798 ms 189860 KB Output is correct
16 Correct 3584 ms 213336 KB Output is correct
17 Correct 2619 ms 191980 KB Output is correct
18 Correct 4619 ms 71484 KB Output is correct
19 Correct 935 ms 71356 KB Output is correct
20 Correct 5182 ms 74068 KB Output is correct
21 Correct 2707 ms 71892 KB Output is correct
22 Correct 5708 ms 188720 KB Output is correct
23 Correct 3963 ms 189236 KB Output is correct
24 Correct 7310 ms 191108 KB Output is correct
25 Correct 7470 ms 193056 KB Output is correct
26 Execution timed out 8047 ms 191828 KB Time limit exceeded
27 Halted 0 ms 0 KB -