oj.uz

Submission #889229

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 100;
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 97 ms 37468 KB Output is correct
2 Correct 939 ms 41848 KB Output is correct
3 Correct 2071 ms 42124 KB Output is correct
4 Correct 579 ms 41868 KB Output is correct
5 Correct 1022 ms 42160 KB Output is correct
6 Correct 546 ms 41888 KB Output is correct
7 Correct 2019 ms 41880 KB Output is correct
8 Correct 2711 ms 41808 KB Output is correct
9 Correct 1037 ms 42440 KB Output is correct
10 Correct 640 ms 41872 KB Output is correct
11 Correct 2045 ms 41880 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35420 KB Output is correct
2 Correct 1261 ms 189572 KB Output is correct
3 Correct 3489 ms 191876 KB Output is correct
4 Correct 814 ms 189876 KB Output is correct
5 Correct 3715 ms 213332 KB Output is correct
6 Correct 2785 ms 191984 KB Output is correct
7 Correct 4908 ms 71480 KB Output is correct
8 Correct 1060 ms 71416 KB Output is correct
9 Correct 5361 ms 74060 KB Output is correct
10 Correct 3040 ms 71896 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 37468 KB Output is correct
2 Correct 939 ms 41848 KB Output is correct
3 Correct 2071 ms 42124 KB Output is correct
4 Correct 579 ms 41868 KB Output is correct
5 Correct 1022 ms 42160 KB Output is correct
6 Correct 546 ms 41888 KB Output is correct
7 Correct 2019 ms 41880 KB Output is correct
8 Correct 2711 ms 41808 KB Output is correct
9 Correct 1037 ms 42440 KB Output is correct
10 Correct 640 ms 41872 KB Output is correct
11 Correct 2045 ms 41880 KB Output is correct
12 Correct 9 ms 35420 KB Output is correct
13 Correct 1261 ms 189572 KB Output is correct
14 Correct 3489 ms 191876 KB Output is correct
15 Correct 814 ms 189876 KB Output is correct
16 Correct 3715 ms 213332 KB Output is correct
17 Correct 2785 ms 191984 KB Output is correct
18 Correct 4908 ms 71480 KB Output is correct
19 Correct 1060 ms 71416 KB Output is correct
20 Correct 5361 ms 74060 KB Output is correct
21 Correct 3040 ms 71896 KB Output is correct
22 Correct 6336 ms 188212 KB Output is correct
23 Correct 3811 ms 189236 KB Output is correct
24 Correct 7904 ms 191216 KB Output is correct
25 Correct 7127 ms 217708 KB Output is correct
26 Execution timed out 8016 ms 215632 KB Time limit exceeded
27 Halted 0 ms 0 KB -