oj.uz

Submission #889234

# Submission time Handle Problem Language Result Execution time Memory
889234 2023-12-19T08:27:04 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 213340 KB 
#include <bits/stdc++.h>
#include <factories.h>
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 75;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long 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 ans = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L; i++)
		if ((1 << i) & (h[v] - h[u])) {
			ans += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return ans;

	for (int i = L - 1; i >= 0; i--)
		if (par[v][i] != par[u][i]) {
			ans += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return ans + 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];
		}
	for (int i = 0; i < N; dis[i++] = I);
}

long long Query(int S, int X[], int T, int Y[]) {
	if (S < Q) {
		long long ans = I;
		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 < S; i++) 
		dis[X[i] + 1] = 0;
	dfsu(1, 0);
	dfsd(1, 0);

	long long ans = I;
	for (int i = 0; i < T; i++) ans = min(ans, dis[Y[i] + 1]);
	for (int i = 0; i < N; dis[i++] = I);
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37560 KB Output is correct
2 Correct 716 ms 41856 KB Output is correct
3 Correct 2076 ms 41876 KB Output is correct
4 Correct 557 ms 41884 KB Output is correct
5 Correct 896 ms 42160 KB Output is correct
6 Correct 535 ms 41872 KB Output is correct
7 Correct 2100 ms 41884 KB Output is correct
8 Correct 2229 ms 41892 KB Output is correct
9 Correct 908 ms 42384 KB Output is correct
10 Correct 540 ms 41864 KB Output is correct
11 Correct 2029 ms 41876 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 1239 ms 189240 KB Output is correct
3 Correct 3378 ms 191944 KB Output is correct
4 Correct 940 ms 189876 KB Output is correct
5 Correct 3544 ms 213340 KB Output is correct
6 Correct 2784 ms 191980 KB Output is correct
7 Correct 4886 ms 71476 KB Output is correct
8 Correct 994 ms 71356 KB Output is correct
9 Correct 5400 ms 74060 KB Output is correct
10 Correct 2909 ms 71760 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37560 KB Output is correct
2 Correct 716 ms 41856 KB Output is correct
3 Correct 2076 ms 41876 KB Output is correct
4 Correct 557 ms 41884 KB Output is correct
5 Correct 896 ms 42160 KB Output is correct
6 Correct 535 ms 41872 KB Output is correct
7 Correct 2100 ms 41884 KB Output is correct
8 Correct 2229 ms 41892 KB Output is correct
9 Correct 908 ms 42384 KB Output is correct
10 Correct 540 ms 41864 KB Output is correct
11 Correct 2029 ms 41876 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1239 ms 189240 KB Output is correct
14 Correct 3378 ms 191944 KB Output is correct
15 Correct 940 ms 189876 KB Output is correct
16 Correct 3544 ms 213340 KB Output is correct
17 Correct 2784 ms 191980 KB Output is correct
18 Correct 4886 ms 71476 KB Output is correct
19 Correct 994 ms 71356 KB Output is correct
20 Correct 5400 ms 74060 KB Output is correct
21 Correct 2909 ms 71760 KB Output is correct
22 Correct 6667 ms 188468 KB Output is correct
23 Correct 4249 ms 189276 KB Output is correct
24 Correct 7541 ms 191052 KB Output is correct
25 Correct 7374 ms 193052 KB Output is correct
26 Execution timed out 8090 ms 191472 KB Time limit exceeded
27 Halted 0 ms 0 KB -