oj.uz

Submission #890091

# Submission time Handle Problem Language Result Execution time Memory
890091 2023-12-20T14:04:31 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 197828 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma GCC optimize("Ofast")
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 41 ms 35420 KB Output is correct
2 Correct 583 ms 41844 KB Output is correct
3 Correct 1083 ms 41856 KB Output is correct
4 Correct 329 ms 41808 KB Output is correct
5 Correct 627 ms 42120 KB Output is correct
6 Correct 870 ms 42068 KB Output is correct
7 Correct 1127 ms 41852 KB Output is correct
8 Correct 1211 ms 41860 KB Output is correct
9 Correct 640 ms 41976 KB Output is correct
10 Correct 847 ms 41864 KB Output is correct
11 Correct 1061 ms 41860 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 1242 ms 186932 KB Output is correct
3 Correct 2238 ms 188260 KB Output is correct
4 Correct 810 ms 187832 KB Output is correct
5 Correct 3037 ms 197828 KB Output is correct
6 Correct 1919 ms 188496 KB Output is correct
7 Correct 2003 ms 69260 KB Output is correct
8 Correct 994 ms 69304 KB Output is correct
9 Correct 3116 ms 70384 KB Output is correct
10 Correct 1524 ms 69552 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 35420 KB Output is correct
2 Correct 583 ms 41844 KB Output is correct
3 Correct 1083 ms 41856 KB Output is correct
4 Correct 329 ms 41808 KB Output is correct
5 Correct 627 ms 42120 KB Output is correct
6 Correct 870 ms 42068 KB Output is correct
7 Correct 1127 ms 41852 KB Output is correct
8 Correct 1211 ms 41860 KB Output is correct
9 Correct 640 ms 41976 KB Output is correct
10 Correct 847 ms 41864 KB Output is correct
11 Correct 1061 ms 41860 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1242 ms 186932 KB Output is correct
14 Correct 2238 ms 188260 KB Output is correct
15 Correct 810 ms 187832 KB Output is correct
16 Correct 3037 ms 197828 KB Output is correct
17 Correct 1919 ms 188496 KB Output is correct
18 Correct 2003 ms 69260 KB Output is correct
19 Correct 994 ms 69304 KB Output is correct
20 Correct 3116 ms 70384 KB Output is correct
21 Correct 1524 ms 69552 KB Output is correct
22 Correct 6175 ms 188272 KB Output is correct
23 Correct 3809 ms 189480 KB Output is correct
24 Correct 7144 ms 189276 KB Output is correct
25 Correct 6957 ms 190884 KB Output is correct
26 Execution timed out 8016 ms 189524 KB Time limit exceeded
27 Halted 0 ms 0 KB -