oj.uz

답안 #889204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
889204 2023-12-19T07:38:09 Z Onown 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 215284 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);
		}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 35416 KB Output is correct
2 Correct 880 ms 41872 KB Output is correct
3 Correct 1981 ms 42116 KB Output is correct
4 Correct 552 ms 41868 KB Output is correct
5 Correct 1165 ms 42172 KB Output is correct
6 Correct 586 ms 41872 KB Output is correct
7 Correct 2067 ms 41892 KB Output is correct
8 Correct 3076 ms 41888 KB Output is correct
9 Correct 1177 ms 42320 KB Output is correct
10 Correct 627 ms 42072 KB Output is correct
11 Correct 2020 ms 41880 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1225 ms 189044 KB Output is correct
3 Correct 3416 ms 191880 KB Output is correct
4 Correct 839 ms 189848 KB Output is correct
5 Correct 3533 ms 213360 KB Output is correct
6 Correct 2581 ms 191976 KB Output is correct
7 Correct 4527 ms 71480 KB Output is correct
8 Correct 930 ms 71360 KB Output is correct
9 Correct 5086 ms 74056 KB Output is correct
10 Correct 2760 ms 71900 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 97 ms 35416 KB Output is correct
2 Correct 880 ms 41872 KB Output is correct
3 Correct 1981 ms 42116 KB Output is correct
4 Correct 552 ms 41868 KB Output is correct
5 Correct 1165 ms 42172 KB Output is correct
6 Correct 586 ms 41872 KB Output is correct
7 Correct 2067 ms 41892 KB Output is correct
8 Correct 3076 ms 41888 KB Output is correct
9 Correct 1177 ms 42320 KB Output is correct
10 Correct 627 ms 42072 KB Output is correct
11 Correct 2020 ms 41880 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1225 ms 189044 KB Output is correct
14 Correct 3416 ms 191880 KB Output is correct
15 Correct 839 ms 189848 KB Output is correct
16 Correct 3533 ms 213360 KB Output is correct
17 Correct 2581 ms 191976 KB Output is correct
18 Correct 4527 ms 71480 KB Output is correct
19 Correct 930 ms 71360 KB Output is correct
20 Correct 5086 ms 74056 KB Output is correct
21 Correct 2760 ms 71900 KB Output is correct
22 Correct 5947 ms 188220 KB Output is correct
23 Correct 3915 ms 214148 KB Output is correct
24 Execution timed out 8005 ms 215284 KB Time limit exceeded
25 Halted 0 ms 0 KB -