oj.uz

답안 #890072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890072 2023-12-20T13:41:18 Z Onown 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 209360 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma GCC optimize("Ofast")
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

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 35672 KB Output is correct
2 Correct 1031 ms 46932 KB Output is correct
3 Correct 1318 ms 46932 KB Output is correct
4 Correct 519 ms 46964 KB Output is correct
5 Correct 1369 ms 46976 KB Output is correct
6 Correct 678 ms 46840 KB Output is correct
7 Correct 1108 ms 46720 KB Output is correct
8 Correct 3931 ms 46724 KB Output is correct
9 Correct 1369 ms 46736 KB Output is correct
10 Correct 678 ms 46980 KB Output is correct
11 Correct 1163 ms 46672 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1193 ms 198700 KB Output is correct
3 Correct 3270 ms 199504 KB Output is correct
4 Correct 805 ms 199348 KB Output is correct
5 Correct 3350 ms 209360 KB Output is correct
6 Correct 2525 ms 200180 KB Output is correct
7 Correct 4446 ms 78316 KB Output is correct
8 Correct 911 ms 78588 KB Output is correct
9 Correct 4764 ms 79596 KB Output is correct
10 Correct 2790 ms 78928 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 35672 KB Output is correct
2 Correct 1031 ms 46932 KB Output is correct
3 Correct 1318 ms 46932 KB Output is correct
4 Correct 519 ms 46964 KB Output is correct
5 Correct 1369 ms 46976 KB Output is correct
6 Correct 678 ms 46840 KB Output is correct
7 Correct 1108 ms 46720 KB Output is correct
8 Correct 3931 ms 46724 KB Output is correct
9 Correct 1369 ms 46736 KB Output is correct
10 Correct 678 ms 46980 KB Output is correct
11 Correct 1163 ms 46672 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1193 ms 198700 KB Output is correct
14 Correct 3270 ms 199504 KB Output is correct
15 Correct 805 ms 199348 KB Output is correct
16 Correct 3350 ms 209360 KB Output is correct
17 Correct 2525 ms 200180 KB Output is correct
18 Correct 4446 ms 78316 KB Output is correct
19 Correct 911 ms 78588 KB Output is correct
20 Correct 4764 ms 79596 KB Output is correct
21 Correct 2790 ms 78928 KB Output is correct
22 Correct 6295 ms 200508 KB Output is correct
23 Correct 3755 ms 201780 KB Output is correct
24 Correct 7717 ms 201812 KB Output is correct
25 Correct 6454 ms 203856 KB Output is correct
26 Execution timed out 8090 ms 201812 KB Time limit exceeded
27 Halted 0 ms 0 KB -