oj.uz

답안 #890423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
890423 2023-12-21T07:20:22 Z Onown 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 216028 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("unroll-loops")
#pragma  GCC optimize ("Ofast")
using namespace std;
 
const int N = 5e5 + 55, L = 2e0 + 20;
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 (int i = 0; i < (int)adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == (int)adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}
 
		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]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}
 
void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		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 && par[v][0] != par[u][0]; 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 (4LL * S * T < N) {
		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 37 ms 35676 KB Output is correct
2 Correct 611 ms 49264 KB Output is correct
3 Correct 3813 ms 47232 KB Output is correct
4 Correct 414 ms 49288 KB Output is correct
5 Correct 628 ms 49444 KB Output is correct
6 Correct 525 ms 49284 KB Output is correct
7 Correct 3893 ms 47228 KB Output is correct
8 Correct 371 ms 49128 KB Output is correct
9 Correct 619 ms 49516 KB Output is correct
10 Correct 549 ms 49748 KB Output is correct
11 Correct 3800 ms 47232 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 35420 KB Output is correct
2 Correct 1327 ms 194980 KB Output is correct
3 Correct 2231 ms 196080 KB Output is correct
4 Correct 661 ms 194264 KB Output is correct
5 Correct 2913 ms 212656 KB Output is correct
6 Correct 1791 ms 203460 KB Output is correct
7 Correct 1901 ms 80012 KB Output is correct
8 Correct 593 ms 80052 KB Output is correct
9 Correct 2722 ms 82060 KB Output is correct
10 Correct 1414 ms 80464 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 35676 KB Output is correct
2 Correct 611 ms 49264 KB Output is correct
3 Correct 3813 ms 47232 KB Output is correct
4 Correct 414 ms 49288 KB Output is correct
5 Correct 628 ms 49444 KB Output is correct
6 Correct 525 ms 49284 KB Output is correct
7 Correct 3893 ms 47228 KB Output is correct
8 Correct 371 ms 49128 KB Output is correct
9 Correct 619 ms 49516 KB Output is correct
10 Correct 549 ms 49748 KB Output is correct
11 Correct 3800 ms 47232 KB Output is correct
12 Correct 8 ms 35420 KB Output is correct
13 Correct 1327 ms 194980 KB Output is correct
14 Correct 2231 ms 196080 KB Output is correct
15 Correct 661 ms 194264 KB Output is correct
16 Correct 2913 ms 212656 KB Output is correct
17 Correct 1791 ms 203460 KB Output is correct
18 Correct 1901 ms 80012 KB Output is correct
19 Correct 593 ms 80052 KB Output is correct
20 Correct 2722 ms 82060 KB Output is correct
21 Correct 1414 ms 80464 KB Output is correct
22 Correct 4127 ms 206652 KB Output is correct
23 Correct 2836 ms 208176 KB Output is correct
24 Correct 6600 ms 208220 KB Output is correct
25 Correct 6129 ms 216028 KB Output is correct
26 Execution timed out 8099 ms 214244 KB Time limit exceeded
27 Halted 0 ms 0 KB -