oj.uz

Submission #890113

# Submission time Handle Problem Language Result Execution time Memory
890113 2023-12-20T14:47:51 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, Q = 140;
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 581 ms 42068 KB Output is correct
3 Correct 1024 ms 41860 KB Output is correct
4 Correct 613 ms 42064 KB Output is correct
5 Correct 613 ms 42024 KB Output is correct
6 Correct 957 ms 41864 KB Output is correct
7 Correct 945 ms 41864 KB Output is correct
8 Correct 597 ms 41864 KB Output is correct
9 Correct 606 ms 42072 KB Output is correct
10 Correct 928 ms 41864 KB Output is correct
11 Correct 994 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 1220 ms 187008 KB Output is correct
3 Correct 2192 ms 188916 KB Output is correct
4 Correct 823 ms 187808 KB Output is correct
5 Correct 2984 ms 204556 KB Output is correct
6 Correct 1886 ms 189120 KB Output is correct
7 Correct 2024 ms 69256 KB Output is correct
8 Correct 939 ms 69376 KB Output is correct
9 Correct 2817 ms 71352 KB Output is correct
10 Correct 1404 ms 69696 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 581 ms 42068 KB Output is correct
3 Correct 1024 ms 41860 KB Output is correct
4 Correct 613 ms 42064 KB Output is correct
5 Correct 613 ms 42024 KB Output is correct
6 Correct 957 ms 41864 KB Output is correct
7 Correct 945 ms 41864 KB Output is correct
8 Correct 597 ms 41864 KB Output is correct
9 Correct 606 ms 42072 KB Output is correct
10 Correct 928 ms 41864 KB Output is correct
11 Correct 994 ms 41860 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1220 ms 187008 KB Output is correct
14 Correct 2192 ms 188916 KB Output is correct
15 Correct 823 ms 187808 KB Output is correct
16 Correct 2984 ms 204556 KB Output is correct
17 Correct 1886 ms 189120 KB Output is correct
18 Correct 2024 ms 69256 KB Output is correct
19 Correct 939 ms 69376 KB Output is correct
20 Correct 2817 ms 71352 KB Output is correct
21 Correct 1404 ms 69696 KB Output is correct
22 Correct 3940 ms 188220 KB Output is correct
23 Correct 3182 ms 189236 KB Output is correct
24 Correct 6385 ms 189732 KB Output is correct
25 Correct 6093 ms 191452 KB Output is correct
26 Execution timed out 8034 ms 190040 KB Time limit exceeded
27 Halted 0 ms 0 KB -