oj.uz

Submission #889231

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 90;
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 90 ms 37712 KB Output is correct
2 Correct 751 ms 41852 KB Output is correct
3 Correct 2060 ms 41876 KB Output is correct
4 Correct 533 ms 41868 KB Output is correct
5 Correct 987 ms 42324 KB Output is correct
6 Correct 497 ms 41872 KB Output is correct
7 Correct 2037 ms 41880 KB Output is correct
8 Correct 2336 ms 42124 KB Output is correct
9 Correct 947 ms 42164 KB Output is correct
10 Correct 498 ms 41812 KB Output is correct
11 Correct 1926 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 1216 ms 189204 KB Output is correct
3 Correct 3303 ms 192120 KB Output is correct
4 Correct 901 ms 189928 KB Output is correct
5 Correct 3658 ms 213352 KB Output is correct
6 Correct 2717 ms 191980 KB Output is correct
7 Correct 4847 ms 71476 KB Output is correct
8 Correct 970 ms 71364 KB Output is correct
9 Correct 4957 ms 74212 KB Output is correct
10 Correct 2782 ms 72080 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 37712 KB Output is correct
2 Correct 751 ms 41852 KB Output is correct
3 Correct 2060 ms 41876 KB Output is correct
4 Correct 533 ms 41868 KB Output is correct
5 Correct 987 ms 42324 KB Output is correct
6 Correct 497 ms 41872 KB Output is correct
7 Correct 2037 ms 41880 KB Output is correct
8 Correct 2336 ms 42124 KB Output is correct
9 Correct 947 ms 42164 KB Output is correct
10 Correct 498 ms 41812 KB Output is correct
11 Correct 1926 ms 41880 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1216 ms 189204 KB Output is correct
14 Correct 3303 ms 192120 KB Output is correct
15 Correct 901 ms 189928 KB Output is correct
16 Correct 3658 ms 213352 KB Output is correct
17 Correct 2717 ms 191980 KB Output is correct
18 Correct 4847 ms 71476 KB Output is correct
19 Correct 970 ms 71364 KB Output is correct
20 Correct 4957 ms 74212 KB Output is correct
21 Correct 2782 ms 72080 KB Output is correct
22 Correct 6022 ms 188268 KB Output is correct
23 Correct 3692 ms 189240 KB Output is correct
24 Correct 7230 ms 191100 KB Output is correct
25 Correct 7418 ms 193060 KB Output is correct
26 Execution timed out 8045 ms 191576 KB Time limit exceeded
27 Halted 0 ms 0 KB -