oj.uz

답안 #890086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890086 2023-12-20T13:58:48 Z Onown 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 197832 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
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 (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 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) {
		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

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 35420 KB Output is correct
2 Correct 584 ms 41852 KB Output is correct
3 Correct 1267 ms 42064 KB Output is correct
4 Correct 328 ms 42064 KB Output is correct
5 Correct 606 ms 41864 KB Output is correct
6 Correct 859 ms 41864 KB Output is correct
7 Correct 1204 ms 41868 KB Output is correct
8 Correct 1169 ms 41856 KB Output is correct
9 Correct 634 ms 42060 KB Output is correct
10 Correct 860 ms 41864 KB Output is correct
11 Correct 1157 ms 41856 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 1211 ms 187000 KB Output is correct
3 Correct 2208 ms 188004 KB Output is correct
4 Correct 803 ms 187836 KB Output is correct
5 Correct 2991 ms 197832 KB Output is correct
6 Correct 1864 ms 188496 KB Output is correct
7 Correct 1888 ms 69204 KB Output is correct
8 Correct 983 ms 69304 KB Output is correct
9 Correct 2732 ms 70452 KB Output is correct
10 Correct 1375 ms 69552 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 35420 KB Output is correct
2 Correct 584 ms 41852 KB Output is correct
3 Correct 1267 ms 42064 KB Output is correct
4 Correct 328 ms 42064 KB Output is correct
5 Correct 606 ms 41864 KB Output is correct
6 Correct 859 ms 41864 KB Output is correct
7 Correct 1204 ms 41868 KB Output is correct
8 Correct 1169 ms 41856 KB Output is correct
9 Correct 634 ms 42060 KB Output is correct
10 Correct 860 ms 41864 KB Output is correct
11 Correct 1157 ms 41856 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1211 ms 187000 KB Output is correct
14 Correct 2208 ms 188004 KB Output is correct
15 Correct 803 ms 187836 KB Output is correct
16 Correct 2991 ms 197832 KB Output is correct
17 Correct 1864 ms 188496 KB Output is correct
18 Correct 1888 ms 69204 KB Output is correct
19 Correct 983 ms 69304 KB Output is correct
20 Correct 2732 ms 70452 KB Output is correct
21 Correct 1375 ms 69552 KB Output is correct
22 Correct 5923 ms 188464 KB Output is correct
23 Correct 3685 ms 189012 KB Output is correct
24 Correct 6960 ms 189288 KB Output is correct
25 Correct 6738 ms 190900 KB Output is correct
26 Execution timed out 8029 ms 189280 KB Time limit exceeded
27 Halted 0 ms 0 KB -