oj.uz

Submission #890079

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 158;
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; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];

			if (res > ans) return res;
		}
	if (v == u) return res;

	for (int i = L - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];

			if (res > ans) return res;
		}
	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 36 ms 35416 KB Output is correct
2 Correct 576 ms 41868 KB Output is correct
3 Correct 1341 ms 41852 KB Output is correct
4 Correct 323 ms 41812 KB Output is correct
5 Correct 545 ms 41808 KB Output is correct
6 Correct 715 ms 41872 KB Output is correct
7 Correct 1228 ms 41860 KB Output is correct
8 Correct 1195 ms 41856 KB Output is correct
9 Correct 539 ms 41976 KB Output is correct
10 Correct 723 ms 41860 KB Output is correct
11 Correct 1268 ms 42068 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 1311 ms 186940 KB Output is correct
3 Correct 2369 ms 188008 KB Output is correct
4 Correct 885 ms 187804 KB Output is correct
5 Correct 3031 ms 197832 KB Output is correct
6 Correct 1815 ms 188320 KB Output is correct
7 Correct 1879 ms 69096 KB Output is correct
8 Correct 1033 ms 69404 KB Output is correct
9 Correct 2485 ms 70628 KB Output is correct
10 Correct 1421 ms 69556 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 35416 KB Output is correct
2 Correct 576 ms 41868 KB Output is correct
3 Correct 1341 ms 41852 KB Output is correct
4 Correct 323 ms 41812 KB Output is correct
5 Correct 545 ms 41808 KB Output is correct
6 Correct 715 ms 41872 KB Output is correct
7 Correct 1228 ms 41860 KB Output is correct
8 Correct 1195 ms 41856 KB Output is correct
9 Correct 539 ms 41976 KB Output is correct
10 Correct 723 ms 41860 KB Output is correct
11 Correct 1268 ms 42068 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1311 ms 186940 KB Output is correct
14 Correct 2369 ms 188008 KB Output is correct
15 Correct 885 ms 187804 KB Output is correct
16 Correct 3031 ms 197832 KB Output is correct
17 Correct 1815 ms 188320 KB Output is correct
18 Correct 1879 ms 69096 KB Output is correct
19 Correct 1033 ms 69404 KB Output is correct
20 Correct 2485 ms 70628 KB Output is correct
21 Correct 1421 ms 69556 KB Output is correct
22 Correct 6293 ms 188212 KB Output is correct
23 Correct 3906 ms 189240 KB Output is correct
24 Correct 7279 ms 189272 KB Output is correct
25 Correct 7054 ms 190896 KB Output is correct
26 Execution timed out 8023 ms 189316 KB Time limit exceeded
27 Halted 0 ms 0 KB -