oj.uz

Submission #889196

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 1e2 + 12;
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);
		}
}

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;
	}
	
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	for (int i = 0; i < S; i++) {
		dis[X[i] + 1] = 0;
		pq.push({0, X[i] + 1});
	}
	while (!pq.empty()) {
		long long d = pq.top().first;
		int v = pq.top().second;
		pq.pop();
		
		if (dis[v] < d) 
		continue;

		for (auto [u, w]: adj[v])
			if (dis[u] > d + w) {
				dis[u] = d + w;
				pq.push({d + w, u});
			}
	}

	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 98 ms 35420 KB Output is correct
2 Correct 1315 ms 42148 KB Output is correct
3 Correct 3345 ms 42068 KB Output is correct
4 Correct 724 ms 51632 KB Output is correct
5 Correct 1409 ms 51628 KB Output is correct
6 Correct 1132 ms 51664 KB Output is correct
7 Correct 3194 ms 51388 KB Output is correct
8 Correct 3793 ms 51540 KB Output is correct
9 Correct 1429 ms 51628 KB Output is correct
10 Correct 1146 ms 51692 KB Output is correct
11 Correct 3270 ms 51388 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 1183 ms 188996 KB Output is correct
3 Correct 3271 ms 191876 KB Output is correct
4 Correct 833 ms 190036 KB Output is correct
5 Correct 3582 ms 213340 KB Output is correct
6 Correct 2418 ms 192084 KB Output is correct
7 Correct 4535 ms 71472 KB Output is correct
8 Correct 933 ms 71364 KB Output is correct
9 Correct 4695 ms 74064 KB Output is correct
10 Correct 2713 ms 72064 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35420 KB Output is correct
2 Correct 1315 ms 42148 KB Output is correct
3 Correct 3345 ms 42068 KB Output is correct
4 Correct 724 ms 51632 KB Output is correct
5 Correct 1409 ms 51628 KB Output is correct
6 Correct 1132 ms 51664 KB Output is correct
7 Correct 3194 ms 51388 KB Output is correct
8 Correct 3793 ms 51540 KB Output is correct
9 Correct 1429 ms 51628 KB Output is correct
10 Correct 1146 ms 51692 KB Output is correct
11 Correct 3270 ms 51388 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1183 ms 188996 KB Output is correct
14 Correct 3271 ms 191876 KB Output is correct
15 Correct 833 ms 190036 KB Output is correct
16 Correct 3582 ms 213340 KB Output is correct
17 Correct 2418 ms 192084 KB Output is correct
18 Correct 4535 ms 71472 KB Output is correct
19 Correct 933 ms 71364 KB Output is correct
20 Correct 4695 ms 74064 KB Output is correct
21 Correct 2713 ms 72064 KB Output is correct
22 Execution timed out 8010 ms 216876 KB Time limit exceeded
23 Halted 0 ms 0 KB -