oj.uz

Submission #890109

# Submission time Handle Problem Language Result Execution time Memory
890109 2023-12-20T14:41:46 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204628 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 (int i = 0; i < (int)adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == (int)adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}

		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]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}

void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		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 || T < 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 39 ms 35416 KB Output is correct
2 Correct 724 ms 41816 KB Output is correct
3 Correct 965 ms 41860 KB Output is correct
4 Correct 878 ms 41864 KB Output is correct
5 Correct 751 ms 42220 KB Output is correct
6 Correct 1375 ms 42068 KB Output is correct
7 Correct 985 ms 41872 KB Output is correct
8 Correct 802 ms 41880 KB Output is correct
9 Correct 762 ms 42068 KB Output is correct
10 Correct 1354 ms 41880 KB Output is correct
11 Correct 969 ms 41864 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35672 KB Output is correct
2 Correct 1213 ms 187096 KB Output is correct
3 Correct 2104 ms 188752 KB Output is correct
4 Correct 813 ms 187828 KB Output is correct
5 Correct 2823 ms 204628 KB Output is correct
6 Correct 1770 ms 189264 KB Output is correct
7 Correct 1861 ms 69260 KB Output is correct
8 Correct 922 ms 69316 KB Output is correct
9 Correct 2614 ms 71196 KB Output is correct
10 Correct 1353 ms 69760 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35416 KB Output is correct
2 Correct 724 ms 41816 KB Output is correct
3 Correct 965 ms 41860 KB Output is correct
4 Correct 878 ms 41864 KB Output is correct
5 Correct 751 ms 42220 KB Output is correct
6 Correct 1375 ms 42068 KB Output is correct
7 Correct 985 ms 41872 KB Output is correct
8 Correct 802 ms 41880 KB Output is correct
9 Correct 762 ms 42068 KB Output is correct
10 Correct 1354 ms 41880 KB Output is correct
11 Correct 969 ms 41864 KB Output is correct
12 Correct 8 ms 35672 KB Output is correct
13 Correct 1213 ms 187096 KB Output is correct
14 Correct 2104 ms 188752 KB Output is correct
15 Correct 813 ms 187828 KB Output is correct
16 Correct 2823 ms 204628 KB Output is correct
17 Correct 1770 ms 189264 KB Output is correct
18 Correct 1861 ms 69260 KB Output is correct
19 Correct 922 ms 69316 KB Output is correct
20 Correct 2614 ms 71196 KB Output is correct
21 Correct 1353 ms 69760 KB Output is correct
22 Correct 3922 ms 188216 KB Output is correct
23 Correct 2952 ms 189236 KB Output is correct
24 Correct 6417 ms 189732 KB Output is correct
25 Correct 6089 ms 191448 KB Output is correct
26 Execution timed out 8103 ms 189976 KB Time limit exceeded
27 Halted 0 ms 0 KB -