oj.uz

답안 #890059

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

#pragma  GCC optimize ("O2,unroll-loops")
#pragma  GCC optimize ("Ofast")

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 95 ms 35416 KB Output is correct
2 Correct 995 ms 42064 KB Output is correct
3 Correct 1163 ms 41852 KB Output is correct
4 Correct 503 ms 41864 KB Output is correct
5 Correct 1291 ms 41972 KB Output is correct
6 Correct 714 ms 41864 KB Output is correct
7 Correct 1126 ms 41852 KB Output is correct
8 Correct 3782 ms 41860 KB Output is correct
9 Correct 1289 ms 41980 KB Output is correct
10 Correct 659 ms 41872 KB Output is correct
11 Correct 1148 ms 41864 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 1258 ms 188988 KB Output is correct
3 Correct 3284 ms 190256 KB Output is correct
4 Correct 812 ms 189904 KB Output is correct
5 Correct 3372 ms 201388 KB Output is correct
6 Correct 2570 ms 190744 KB Output is correct
7 Correct 4247 ms 71176 KB Output is correct
8 Correct 908 ms 71560 KB Output is correct
9 Correct 4427 ms 72604 KB Output is correct
10 Correct 2580 ms 71860 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 35416 KB Output is correct
2 Correct 995 ms 42064 KB Output is correct
3 Correct 1163 ms 41852 KB Output is correct
4 Correct 503 ms 41864 KB Output is correct
5 Correct 1291 ms 41972 KB Output is correct
6 Correct 714 ms 41864 KB Output is correct
7 Correct 1126 ms 41852 KB Output is correct
8 Correct 3782 ms 41860 KB Output is correct
9 Correct 1289 ms 41980 KB Output is correct
10 Correct 659 ms 41872 KB Output is correct
11 Correct 1148 ms 41864 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1258 ms 188988 KB Output is correct
14 Correct 3284 ms 190256 KB Output is correct
15 Correct 812 ms 189904 KB Output is correct
16 Correct 3372 ms 201388 KB Output is correct
17 Correct 2570 ms 190744 KB Output is correct
18 Correct 4247 ms 71176 KB Output is correct
19 Correct 908 ms 71560 KB Output is correct
20 Correct 4427 ms 72604 KB Output is correct
21 Correct 2580 ms 71860 KB Output is correct
22 Correct 6161 ms 188544 KB Output is correct
23 Correct 3922 ms 189272 KB Output is correct
24 Execution timed out 8022 ms 189312 KB Time limit exceeded
25 Halted 0 ms 0 KB -