oj.uz

Submission #889205

# Submission time Handle Problem Language Result Execution time Memory
889205 2023-12-19T07:43:45 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 213368 KB 
#include <bits/stdc++.h>
#include <factories.h>
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 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 112 ms 35508 KB Output is correct
2 Correct 1164 ms 41856 KB Output is correct
3 Correct 2004 ms 41880 KB Output is correct
4 Correct 618 ms 41872 KB Output is correct
5 Correct 1592 ms 42320 KB Output is correct
6 Correct 757 ms 41868 KB Output is correct
7 Correct 2005 ms 41880 KB Output is correct
8 Correct 4683 ms 41808 KB Output is correct
9 Correct 1511 ms 42160 KB Output is correct
10 Correct 762 ms 42080 KB Output is correct
11 Correct 1969 ms 41868 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 1271 ms 189204 KB Output is correct
3 Correct 3358 ms 191876 KB Output is correct
4 Correct 836 ms 189920 KB Output is correct
5 Correct 3512 ms 213368 KB Output is correct
6 Correct 2608 ms 192044 KB Output is correct
7 Correct 4715 ms 71484 KB Output is correct
8 Correct 947 ms 71424 KB Output is correct
9 Correct 5178 ms 74060 KB Output is correct
10 Correct 3205 ms 71908 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 35508 KB Output is correct
2 Correct 1164 ms 41856 KB Output is correct
3 Correct 2004 ms 41880 KB Output is correct
4 Correct 618 ms 41872 KB Output is correct
5 Correct 1592 ms 42320 KB Output is correct
6 Correct 757 ms 41868 KB Output is correct
7 Correct 2005 ms 41880 KB Output is correct
8 Correct 4683 ms 41808 KB Output is correct
9 Correct 1511 ms 42160 KB Output is correct
10 Correct 762 ms 42080 KB Output is correct
11 Correct 1969 ms 41868 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1271 ms 189204 KB Output is correct
14 Correct 3358 ms 191876 KB Output is correct
15 Correct 836 ms 189920 KB Output is correct
16 Correct 3512 ms 213368 KB Output is correct
17 Correct 2608 ms 192044 KB Output is correct
18 Correct 4715 ms 71484 KB Output is correct
19 Correct 947 ms 71424 KB Output is correct
20 Correct 5178 ms 74060 KB Output is correct
21 Correct 3205 ms 71908 KB Output is correct
22 Correct 6135 ms 188212 KB Output is correct
23 Correct 3844 ms 189232 KB Output is correct
24 Execution timed out 8042 ms 191116 KB Time limit exceeded
25 Halted 0 ms 0 KB -