oj.uz

Submission #890112

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

const int N = 5e5 + 55, L = 2e0 + 20, Q = 155;
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 (int i = 0; i < (int)adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == (int)adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}

		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]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}

void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		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 && res < ans; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return res;

	for (int i = L - 1; i >= 0 && res < ans; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	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 || T < 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 39 ms 35420 KB Output is correct
2 Correct 635 ms 42064 KB Output is correct
3 Correct 1000 ms 41856 KB Output is correct
4 Correct 753 ms 41872 KB Output is correct
5 Correct 657 ms 42016 KB Output is correct
6 Correct 1083 ms 41864 KB Output is correct
7 Correct 991 ms 41868 KB Output is correct
8 Correct 687 ms 41868 KB Output is correct
9 Correct 648 ms 42068 KB Output is correct
10 Correct 1097 ms 41868 KB Output is correct
11 Correct 988 ms 41856 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35616 KB Output is correct
2 Correct 1222 ms 187188 KB Output is correct
3 Correct 2149 ms 188916 KB Output is correct
4 Correct 823 ms 187800 KB Output is correct
5 Correct 2960 ms 204560 KB Output is correct
6 Correct 1961 ms 189120 KB Output is correct
7 Correct 1952 ms 69264 KB Output is correct
8 Correct 1006 ms 69296 KB Output is correct
9 Correct 2930 ms 71188 KB Output is correct
10 Correct 1446 ms 69712 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35420 KB Output is correct
2 Correct 635 ms 42064 KB Output is correct
3 Correct 1000 ms 41856 KB Output is correct
4 Correct 753 ms 41872 KB Output is correct
5 Correct 657 ms 42016 KB Output is correct
6 Correct 1083 ms 41864 KB Output is correct
7 Correct 991 ms 41868 KB Output is correct
8 Correct 687 ms 41868 KB Output is correct
9 Correct 648 ms 42068 KB Output is correct
10 Correct 1097 ms 41868 KB Output is correct
11 Correct 988 ms 41856 KB Output is correct
12 Correct 7 ms 35616 KB Output is correct
13 Correct 1222 ms 187188 KB Output is correct
14 Correct 2149 ms 188916 KB Output is correct
15 Correct 823 ms 187800 KB Output is correct
16 Correct 2960 ms 204560 KB Output is correct
17 Correct 1961 ms 189120 KB Output is correct
18 Correct 1952 ms 69264 KB Output is correct
19 Correct 1006 ms 69296 KB Output is correct
20 Correct 2930 ms 71188 KB Output is correct
21 Correct 1446 ms 69712 KB Output is correct
22 Correct 4159 ms 188212 KB Output is correct
23 Correct 3232 ms 189244 KB Output is correct
24 Correct 6592 ms 189720 KB Output is correct
25 Correct 6432 ms 191436 KB Output is correct
26 Execution timed out 8052 ms 189976 KB Time limit exceeded
27 Halted 0 ms 0 KB -