oj.uz

Submission #899559

# Submission time Handle Problem Language Result Execution time Memory
899559 2024-01-06T12:58:05 Z Onown Factories (JOI14_factories) C++17
18 / 100
 895 ms 259156 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 < 3LL * 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;
	}

	memset(dis, 255, sizeof dis);
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 38744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35420 KB Output is correct
2 Correct 816 ms 240080 KB Output is correct
3 Correct 853 ms 237540 KB Output is correct
4 Correct 689 ms 235956 KB Output is correct
5 Correct 836 ms 259156 KB Output is correct
6 Correct 804 ms 237908 KB Output is correct
7 Correct 895 ms 81120 KB Output is correct
8 Correct 560 ms 80704 KB Output is correct
9 Correct 548 ms 83672 KB Output is correct
10 Correct 619 ms 81488 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 38744 KB Output isn't correct
2 Halted 0 ms 0 KB -