oj.uz

답안 #890084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890084 2023-12-20T13:55:29 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 = 180;
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 40 ms 35420 KB Output is correct
2 Correct 554 ms 41888 KB Output is correct
3 Correct 1384 ms 41864 KB Output is correct
4 Correct 317 ms 41812 KB Output is correct
5 Correct 598 ms 41976 KB Output is correct
6 Correct 882 ms 41860 KB Output is correct
7 Correct 1103 ms 41856 KB Output is correct
8 Correct 1172 ms 41808 KB Output is correct
9 Correct 655 ms 41812 KB Output is correct
10 Correct 854 ms 41812 KB Output is correct
11 Correct 1165 ms 41856 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35672 KB Output is correct
2 Correct 1196 ms 186940 KB Output is correct
3 Correct 2183 ms 188256 KB Output is correct
4 Correct 828 ms 187864 KB Output is correct
5 Correct 3036 ms 197832 KB Output is correct
6 Correct 1964 ms 188320 KB Output is correct
7 Correct 1939 ms 69088 KB Output is correct
8 Correct 1012 ms 69300 KB Output is correct
9 Correct 2973 ms 70380 KB Output is correct
10 Correct 1391 ms 69772 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 35420 KB Output is correct
2 Correct 554 ms 41888 KB Output is correct
3 Correct 1384 ms 41864 KB Output is correct
4 Correct 317 ms 41812 KB Output is correct
5 Correct 598 ms 41976 KB Output is correct
6 Correct 882 ms 41860 KB Output is correct
7 Correct 1103 ms 41856 KB Output is correct
8 Correct 1172 ms 41808 KB Output is correct
9 Correct 655 ms 41812 KB Output is correct
10 Correct 854 ms 41812 KB Output is correct
11 Correct 1165 ms 41856 KB Output is correct
12 Correct 7 ms 35672 KB Output is correct
13 Correct 1196 ms 186940 KB Output is correct
14 Correct 2183 ms 188256 KB Output is correct
15 Correct 828 ms 187864 KB Output is correct
16 Correct 3036 ms 197832 KB Output is correct
17 Correct 1964 ms 188320 KB Output is correct
18 Correct 1939 ms 69088 KB Output is correct
19 Correct 1012 ms 69300 KB Output is correct
20 Correct 2973 ms 70380 KB Output is correct
21 Correct 1391 ms 69772 KB Output is correct
22 Correct 6171 ms 188220 KB Output is correct
23 Correct 3801 ms 189268 KB Output is correct
24 Correct 7125 ms 189280 KB Output is correct
25 Correct 6991 ms 190924 KB Output is correct
26 Execution timed out 8004 ms 189268 KB Time limit exceeded
27 Halted 0 ms 0 KB -