oj.uz

Submission #890056

# Submission time Handle Problem Language Result Execution time Memory
890056 2023-12-20T12:43:23 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 213344 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 101 ms 35760 KB Output is correct
2 Correct 1143 ms 41868 KB Output is correct
3 Correct 1984 ms 41872 KB Output is correct
4 Correct 589 ms 41868 KB Output is correct
5 Correct 1476 ms 42160 KB Output is correct
6 Correct 768 ms 41816 KB Output is correct
7 Correct 1930 ms 41876 KB Output is correct
8 Correct 4503 ms 41892 KB Output is correct
9 Correct 1521 ms 42168 KB Output is correct
10 Correct 771 ms 42064 KB Output is correct
11 Correct 1941 ms 41884 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 1203 ms 189120 KB Output is correct
3 Correct 3265 ms 191880 KB Output is correct
4 Correct 808 ms 189912 KB Output is correct
5 Correct 3420 ms 213344 KB Output is correct
6 Correct 2452 ms 192336 KB Output is correct
7 Correct 4335 ms 71484 KB Output is correct
8 Correct 945 ms 71356 KB Output is correct
9 Correct 4503 ms 74060 KB Output is correct
10 Correct 2710 ms 71900 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 35760 KB Output is correct
2 Correct 1143 ms 41868 KB Output is correct
3 Correct 1984 ms 41872 KB Output is correct
4 Correct 589 ms 41868 KB Output is correct
5 Correct 1476 ms 42160 KB Output is correct
6 Correct 768 ms 41816 KB Output is correct
7 Correct 1930 ms 41876 KB Output is correct
8 Correct 4503 ms 41892 KB Output is correct
9 Correct 1521 ms 42168 KB Output is correct
10 Correct 771 ms 42064 KB Output is correct
11 Correct 1941 ms 41884 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 1203 ms 189120 KB Output is correct
14 Correct 3265 ms 191880 KB Output is correct
15 Correct 808 ms 189912 KB Output is correct
16 Correct 3420 ms 213344 KB Output is correct
17 Correct 2452 ms 192336 KB Output is correct
18 Correct 4335 ms 71484 KB Output is correct
19 Correct 945 ms 71356 KB Output is correct
20 Correct 4503 ms 74060 KB Output is correct
21 Correct 2710 ms 71900 KB Output is correct
22 Correct 6152 ms 188376 KB Output is correct
23 Correct 3565 ms 189060 KB Output is correct
24 Correct 7823 ms 191148 KB Output is correct
25 Correct 6896 ms 193056 KB Output is correct
26 Execution timed out 8010 ms 191568 KB Time limit exceeded
27 Halted 0 ms 0 KB -