oj.uz

Submission #899567

# Submission time Handle Problem Language Result Execution time Memory
899567 2024-01-06T13:10:32 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 278356 KB 
#include <bits/stdc++.h>
#include <factories.h>
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 (1LL * 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:61:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   61 |    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 12 ms 35672 KB Output is correct
2 Correct 358 ms 51260 KB Output is correct
3 Correct 1086 ms 50624 KB Output is correct
4 Correct 256 ms 50564 KB Output is correct
5 Correct 403 ms 50932 KB Output is correct
6 Correct 209 ms 50608 KB Output is correct
7 Correct 1020 ms 50944 KB Output is correct
8 Correct 264 ms 50888 KB Output is correct
9 Correct 384 ms 51156 KB Output is correct
10 Correct 229 ms 51028 KB Output is correct
11 Correct 1056 ms 50884 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35416 KB Output is correct
2 Correct 824 ms 255316 KB Output is correct
3 Correct 887 ms 256392 KB Output is correct
4 Correct 668 ms 254400 KB Output is correct
5 Correct 836 ms 278356 KB Output is correct
6 Correct 839 ms 257144 KB Output is correct
7 Correct 825 ms 93524 KB Output is correct
8 Correct 585 ms 93636 KB Output is correct
9 Correct 536 ms 96804 KB Output is correct
10 Correct 625 ms 94268 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 35672 KB Output is correct
2 Correct 358 ms 51260 KB Output is correct
3 Correct 1086 ms 50624 KB Output is correct
4 Correct 256 ms 50564 KB Output is correct
5 Correct 403 ms 50932 KB Output is correct
6 Correct 209 ms 50608 KB Output is correct
7 Correct 1020 ms 50944 KB Output is correct
8 Correct 264 ms 50888 KB Output is correct
9 Correct 384 ms 51156 KB Output is correct
10 Correct 229 ms 51028 KB Output is correct
11 Correct 1056 ms 50884 KB Output is correct
12 Correct 6 ms 35416 KB Output is correct
13 Correct 824 ms 255316 KB Output is correct
14 Correct 887 ms 256392 KB Output is correct
15 Correct 668 ms 254400 KB Output is correct
16 Correct 836 ms 278356 KB Output is correct
17 Correct 839 ms 257144 KB Output is correct
18 Correct 825 ms 93524 KB Output is correct
19 Correct 585 ms 93636 KB Output is correct
20 Correct 536 ms 96804 KB Output is correct
21 Correct 625 ms 94268 KB Output is correct
22 Correct 5228 ms 261296 KB Output is correct
23 Correct 2769 ms 263064 KB Output is correct
24 Correct 7749 ms 264096 KB Output is correct
25 Correct 6942 ms 266492 KB Output is correct
26 Execution timed out 8099 ms 264504 KB Time limit exceeded
27 Halted 0 ms 0 KB -