oj.uz

Submission #890124

# Submission time Handle Problem Language Result Execution time Memory
890124 2023-12-20T15:06:26 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204556 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("Ofast")
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20;
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 && par[v][0] != par[u][0]; 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 (3LL * S * T < N) {
		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 40 ms 35416 KB Output is correct
2 Correct 950 ms 41872 KB Output is correct
3 Correct 4124 ms 39804 KB Output is correct
4 Correct 491 ms 41856 KB Output is correct
5 Correct 866 ms 42132 KB Output is correct
6 Correct 821 ms 41868 KB Output is correct
7 Correct 4086 ms 39808 KB Output is correct
8 Correct 450 ms 41864 KB Output is correct
9 Correct 871 ms 42016 KB Output is correct
10 Correct 820 ms 41812 KB Output is correct
11 Correct 4093 ms 39812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 1183 ms 186996 KB Output is correct
3 Correct 2135 ms 189008 KB Output is correct
4 Correct 626 ms 187804 KB Output is correct
5 Correct 2864 ms 204556 KB Output is correct
6 Correct 1795 ms 189312 KB Output is correct
7 Correct 1988 ms 69460 KB Output is correct
8 Correct 541 ms 69308 KB Output is correct
9 Correct 2714 ms 71184 KB Output is correct
10 Correct 1297 ms 69716 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35416 KB Output is correct
2 Correct 950 ms 41872 KB Output is correct
3 Correct 4124 ms 39804 KB Output is correct
4 Correct 491 ms 41856 KB Output is correct
5 Correct 866 ms 42132 KB Output is correct
6 Correct 821 ms 41868 KB Output is correct
7 Correct 4086 ms 39808 KB Output is correct
8 Correct 450 ms 41864 KB Output is correct
9 Correct 871 ms 42016 KB Output is correct
10 Correct 820 ms 41812 KB Output is correct
11 Correct 4093 ms 39812 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1183 ms 186996 KB Output is correct
14 Correct 2135 ms 189008 KB Output is correct
15 Correct 626 ms 187804 KB Output is correct
16 Correct 2864 ms 204556 KB Output is correct
17 Correct 1795 ms 189312 KB Output is correct
18 Correct 1988 ms 69460 KB Output is correct
19 Correct 541 ms 69308 KB Output is correct
20 Correct 2714 ms 71184 KB Output is correct
21 Correct 1297 ms 69716 KB Output is correct
22 Correct 4144 ms 188240 KB Output is correct
23 Correct 2716 ms 189236 KB Output is correct
24 Correct 6149 ms 189736 KB Output is correct
25 Correct 5740 ms 191432 KB Output is correct
26 Execution timed out 8007 ms 190036 KB Time limit exceeded
27 Halted 0 ms 0 KB -