oj.uz

Submission #899575

# Submission time Handle Problem Language Result Execution time Memory
899575 2024-01-06T13:36:13 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 267968 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 (3LL * 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 25 ms 35540 KB Output is correct
2 Correct 649 ms 41908 KB Output is correct
3 Correct 2837 ms 41932 KB Output is correct
4 Correct 353 ms 41812 KB Output is correct
5 Correct 476 ms 42328 KB Output is correct
6 Correct 395 ms 41956 KB Output is correct
7 Correct 2545 ms 42068 KB Output is correct
8 Correct 343 ms 41816 KB Output is correct
9 Correct 468 ms 42224 KB Output is correct
10 Correct 404 ms 42064 KB Output is correct
11 Correct 2547 ms 41936 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35420 KB Output is correct
2 Correct 798 ms 237076 KB Output is correct
3 Correct 860 ms 240724 KB Output is correct
4 Correct 690 ms 237760 KB Output is correct
5 Correct 915 ms 267968 KB Output is correct
6 Correct 790 ms 240744 KB Output is correct
7 Correct 769 ms 81040 KB Output is correct
8 Correct 529 ms 80832 KB Output is correct
9 Correct 547 ms 84428 KB Output is correct
10 Correct 602 ms 81636 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35540 KB Output is correct
2 Correct 649 ms 41908 KB Output is correct
3 Correct 2837 ms 41932 KB Output is correct
4 Correct 353 ms 41812 KB Output is correct
5 Correct 476 ms 42328 KB Output is correct
6 Correct 395 ms 41956 KB Output is correct
7 Correct 2545 ms 42068 KB Output is correct
8 Correct 343 ms 41816 KB Output is correct
9 Correct 468 ms 42224 KB Output is correct
10 Correct 404 ms 42064 KB Output is correct
11 Correct 2547 ms 41936 KB Output is correct
12 Correct 6 ms 35420 KB Output is correct
13 Correct 798 ms 237076 KB Output is correct
14 Correct 860 ms 240724 KB Output is correct
15 Correct 690 ms 237760 KB Output is correct
16 Correct 915 ms 267968 KB Output is correct
17 Correct 790 ms 240744 KB Output is correct
18 Correct 769 ms 81040 KB Output is correct
19 Correct 529 ms 80832 KB Output is correct
20 Correct 547 ms 84428 KB Output is correct
21 Correct 602 ms 81636 KB Output is correct
22 Correct 5726 ms 239096 KB Output is correct
23 Correct 3113 ms 240208 KB Output is correct
24 Correct 6806 ms 241936 KB Output is correct
25 Correct 6370 ms 244012 KB Output is correct
26 Execution timed out 8023 ms 242384 KB Time limit exceeded
27 Halted 0 ms 0 KB -