oj.uz

Submission #890110

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 160;
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 35420 KB Output is correct
2 Correct 651 ms 41844 KB Output is correct
3 Correct 995 ms 41888 KB Output is correct
4 Correct 737 ms 41864 KB Output is correct
5 Correct 664 ms 42016 KB Output is correct
6 Correct 1145 ms 41888 KB Output is correct
7 Correct 950 ms 41856 KB Output is correct
8 Correct 704 ms 42064 KB Output is correct
9 Correct 642 ms 42136 KB Output is correct
10 Correct 1132 ms 41860 KB Output is correct
11 Correct 986 ms 41868 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 1171 ms 187204 KB Output is correct
3 Correct 2071 ms 188916 KB Output is correct
4 Correct 799 ms 188060 KB Output is correct
5 Correct 2849 ms 204808 KB Output is correct
6 Correct 1840 ms 189128 KB Output is correct
7 Correct 1829 ms 69460 KB Output is correct
8 Correct 924 ms 69288 KB Output is correct
9 Correct 2676 ms 71188 KB Output is correct
10 Correct 1318 ms 69700 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35420 KB Output is correct
2 Correct 651 ms 41844 KB Output is correct
3 Correct 995 ms 41888 KB Output is correct
4 Correct 737 ms 41864 KB Output is correct
5 Correct 664 ms 42016 KB Output is correct
6 Correct 1145 ms 41888 KB Output is correct
7 Correct 950 ms 41856 KB Output is correct
8 Correct 704 ms 42064 KB Output is correct
9 Correct 642 ms 42136 KB Output is correct
10 Correct 1132 ms 41860 KB Output is correct
11 Correct 986 ms 41868 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1171 ms 187204 KB Output is correct
14 Correct 2071 ms 188916 KB Output is correct
15 Correct 799 ms 188060 KB Output is correct
16 Correct 2849 ms 204808 KB Output is correct
17 Correct 1840 ms 189128 KB Output is correct
18 Correct 1829 ms 69460 KB Output is correct
19 Correct 924 ms 69288 KB Output is correct
20 Correct 2676 ms 71188 KB Output is correct
21 Correct 1318 ms 69700 KB Output is correct
22 Correct 3834 ms 188472 KB Output is correct
23 Correct 2993 ms 189236 KB Output is correct
24 Correct 6441 ms 189720 KB Output is correct
25 Correct 5901 ms 191452 KB Output is correct
26 Execution timed out 8026 ms 190288 KB Time limit exceeded
27 Halted 0 ms 0 KB -