oj.uz

Submission #899572

# Submission time Handle Problem Language Result Execution time Memory
899572 2024-01-06T13:27:13 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 268172 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

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35420 KB Output is correct
2 Correct 346 ms 41948 KB Output is correct
3 Correct 879 ms 42068 KB Output is correct
4 Correct 303 ms 41808 KB Output is correct
5 Correct 342 ms 42468 KB Output is correct
6 Correct 214 ms 41808 KB Output is correct
7 Correct 630 ms 41936 KB Output is correct
8 Correct 289 ms 41940 KB Output is correct
9 Correct 384 ms 42324 KB Output is correct
10 Correct 212 ms 41956 KB Output is correct
11 Correct 604 ms 42064 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 849 ms 237076 KB Output is correct
3 Correct 877 ms 240644 KB Output is correct
4 Correct 733 ms 237816 KB Output is correct
5 Correct 951 ms 268172 KB Output is correct
6 Correct 829 ms 240644 KB Output is correct
7 Correct 808 ms 81228 KB Output is correct
8 Correct 609 ms 80736 KB Output is correct
9 Correct 566 ms 84436 KB Output is correct
10 Correct 627 ms 81488 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35420 KB Output is correct
2 Correct 346 ms 41948 KB Output is correct
3 Correct 879 ms 42068 KB Output is correct
4 Correct 303 ms 41808 KB Output is correct
5 Correct 342 ms 42468 KB Output is correct
6 Correct 214 ms 41808 KB Output is correct
7 Correct 630 ms 41936 KB Output is correct
8 Correct 289 ms 41940 KB Output is correct
9 Correct 384 ms 42324 KB Output is correct
10 Correct 212 ms 41956 KB Output is correct
11 Correct 604 ms 42064 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 849 ms 237076 KB Output is correct
14 Correct 877 ms 240644 KB Output is correct
15 Correct 733 ms 237816 KB Output is correct
16 Correct 951 ms 268172 KB Output is correct
17 Correct 829 ms 240644 KB Output is correct
18 Correct 808 ms 81228 KB Output is correct
19 Correct 609 ms 80736 KB Output is correct
20 Correct 566 ms 84436 KB Output is correct
21 Correct 627 ms 81488 KB Output is correct
22 Correct 5812 ms 239100 KB Output is correct
23 Correct 3531 ms 240128 KB Output is correct
24 Correct 7235 ms 241940 KB Output is correct
25 Correct 6884 ms 243944 KB Output is correct
26 Execution timed out 8099 ms 242256 KB Time limit exceeded
27 Halted 0 ms 0 KB -