oj.uz

Submission #899561

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

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

/*int main() {
	int nn, qq, aa[10] = {}, bb[10] = {}, dd[10] = {};
	cin >> nn >> qq;
	for (int i = 0; i < nn - 1; i++)
		cin >> aa[i] >> bb[i] >> dd[i];
	Init(nn, aa, bb, dd);

	while (qq--) {
		int ss, xx[10] = {}, tt, yy[10] = {};
		cin >> ss >> tt;
		for (int i = 0; i < ss; i++)
			cin >> xx[i];
		for (int i = 0; i < tt; i++)
			cin >> yy[i];
		cout << Query(ss, xx, tt, yy) << '\n';
	}
}*/

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 100 ms 38540 KB Output is correct
2 Correct 749 ms 50052 KB Output is correct
3 Correct 2724 ms 53664 KB Output is correct
4 Correct 397 ms 53580 KB Output is correct
5 Correct 797 ms 53832 KB Output is correct
6 Correct 602 ms 53580 KB Output is correct
7 Correct 2668 ms 52560 KB Output is correct
8 Correct 403 ms 52564 KB Output is correct
9 Correct 806 ms 52668 KB Output is correct
10 Correct 600 ms 52308 KB Output is correct
11 Correct 2638 ms 52832 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 845 ms 237040 KB Output is correct
3 Correct 940 ms 237568 KB Output is correct
4 Correct 775 ms 235776 KB Output is correct
5 Correct 911 ms 259156 KB Output is correct
6 Correct 894 ms 237808 KB Output is correct
7 Correct 910 ms 80864 KB Output is correct
8 Correct 601 ms 80724 KB Output is correct
9 Correct 534 ms 83540 KB Output is correct
10 Correct 621 ms 81356 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 38540 KB Output is correct
2 Correct 749 ms 50052 KB Output is correct
3 Correct 2724 ms 53664 KB Output is correct
4 Correct 397 ms 53580 KB Output is correct
5 Correct 797 ms 53832 KB Output is correct
6 Correct 602 ms 53580 KB Output is correct
7 Correct 2668 ms 52560 KB Output is correct
8 Correct 403 ms 52564 KB Output is correct
9 Correct 806 ms 52668 KB Output is correct
10 Correct 600 ms 52308 KB Output is correct
11 Correct 2638 ms 52832 KB Output is correct
12 Correct 6 ms 35420 KB Output is correct
13 Correct 845 ms 237040 KB Output is correct
14 Correct 940 ms 237568 KB Output is correct
15 Correct 775 ms 235776 KB Output is correct
16 Correct 911 ms 259156 KB Output is correct
17 Correct 894 ms 237808 KB Output is correct
18 Correct 910 ms 80864 KB Output is correct
19 Correct 601 ms 80724 KB Output is correct
20 Correct 534 ms 83540 KB Output is correct
21 Correct 621 ms 81356 KB Output is correct
22 Correct 5198 ms 255784 KB Output is correct
23 Correct 2605 ms 257372 KB Output is correct
24 Correct 7861 ms 258728 KB Output is correct
25 Correct 6445 ms 261136 KB Output is correct
26 Execution timed out 8034 ms 255244 KB Time limit exceeded
27 Halted 0 ms 0 KB -