oj.uz

답안 #899570

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

#define F first
#define S second
#define PB push_back

const int N = 5e5 + 55, L = 2e0 + 20;
const long long I = 1e18 + 118;
int n, ocr[N], lg[2 * N];
long long tr[N], dis[N];
vector<pair<int, int>> adj[N];
pair<int, int> rmq[2 * N][L];

void dfs(int v, int p, int h) {
	static int plc = 0;
	rmq[ocr[v] = plc++][0] = {h, v};
	for (auto [u, w]: adj[v])
		if (u != p) {
			tr[u] = tr[v] + w;
			dfs(u, v, h + 1);
			rmq[plc++][0] = {h, v};
		}
}

long long distance(int v, int u) {
	if (ocr[v] > ocr[u]) swap(v, u);
	int s = ocr[v], e = ocr[u], t = lg[e - s + 1];
	pair<int, int> hl = min(rmq[s][t], rmq[e - (1 << t) + 1][t]);
	return tr[v] + tr[u] - 2 * tr[hl.S];
}

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);
		}
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
 
 	for (int i = 2; i < 2 * N; i++) lg[i] = lg[i / 2] + 1;
	dfs(0, -1, 0);
	for (int j = 1; j < L; j++)
		for (int i = 0; i + (1 << j) < 2 * n; i++)
			rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
}

long long Query(int S, int X[], int T, int Y[]) {
	long long ans = I;
	if (4LL * S * T < N) {
		for (int i = 0; i < S; i++)
			for (int j = 0; j < T; j++)
				ans = min(ans, distance(X[i], Y[j]));
		return ans;
	}

	for (int i = 0; i < n; dis[i++] = I);
	for (int i = 0; i < S; i++)
		dis[X[i]] = 0;

	dfsu(0, -1);
	dfsd(0, -1);
	for (int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i]]);
	return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:62:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |    rmq[i][j] = min(rmq[i][j - 1], rmq[i + (1 << j - 1)][j - 1]);
      |                                                 ~~^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35420 KB Output is correct
2 Correct 500 ms 41808 KB Output is correct
3 Correct 2738 ms 41928 KB Output is correct
4 Correct 311 ms 41952 KB Output is correct
5 Correct 412 ms 42068 KB Output is correct
6 Correct 329 ms 42068 KB Output is correct
7 Correct 2636 ms 41812 KB Output is correct
8 Correct 308 ms 42068 KB Output is correct
9 Correct 420 ms 42200 KB Output is correct
10 Correct 337 ms 41920 KB Output is correct
11 Correct 2528 ms 41940 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 35420 KB Output is correct
2 Correct 811 ms 237100 KB Output is correct
3 Correct 837 ms 240844 KB Output is correct
4 Correct 654 ms 237628 KB Output is correct
5 Correct 808 ms 267856 KB Output is correct
6 Correct 818 ms 240636 KB Output is correct
7 Correct 764 ms 80976 KB Output is correct
8 Correct 532 ms 80836 KB Output is correct
9 Correct 538 ms 84252 KB Output is correct
10 Correct 602 ms 81492 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 35420 KB Output is correct
2 Correct 500 ms 41808 KB Output is correct
3 Correct 2738 ms 41928 KB Output is correct
4 Correct 311 ms 41952 KB Output is correct
5 Correct 412 ms 42068 KB Output is correct
6 Correct 329 ms 42068 KB Output is correct
7 Correct 2636 ms 41812 KB Output is correct
8 Correct 308 ms 42068 KB Output is correct
9 Correct 420 ms 42200 KB Output is correct
10 Correct 337 ms 41920 KB Output is correct
11 Correct 2528 ms 41940 KB Output is correct
12 Correct 6 ms 35420 KB Output is correct
13 Correct 811 ms 237100 KB Output is correct
14 Correct 837 ms 240844 KB Output is correct
15 Correct 654 ms 237628 KB Output is correct
16 Correct 808 ms 267856 KB Output is correct
17 Correct 818 ms 240636 KB Output is correct
18 Correct 764 ms 80976 KB Output is correct
19 Correct 532 ms 80836 KB Output is correct
20 Correct 538 ms 84252 KB Output is correct
21 Correct 602 ms 81492 KB Output is correct
22 Correct 5861 ms 239100 KB Output is correct
23 Correct 3254 ms 240128 KB Output is correct
24 Correct 7147 ms 242172 KB Output is correct
25 Correct 6309 ms 243944 KB Output is correct
26 Execution timed out 8019 ms 242268 KB Time limit exceeded
27 Halted 0 ms 0 KB -