oj.uz

Submission #899556

# Submission time Handle Problem Language Result Execution time Memory
899556 2024-01-06T12:56:15 Z Onown Factories (JOI14_factories) C++17
18 / 100
 8000 ms 273364 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;
}
/*
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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35672 KB Output is correct
2 Execution timed out 8020 ms 52124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35420 KB Output is correct
2 Correct 1024 ms 244152 KB Output is correct
3 Correct 1042 ms 251592 KB Output is correct
4 Correct 783 ms 249888 KB Output is correct
5 Correct 880 ms 273364 KB Output is correct
6 Correct 871 ms 252520 KB Output is correct
7 Correct 850 ms 91732 KB Output is correct
8 Correct 529 ms 91588 KB Output is correct
9 Correct 526 ms 94284 KB Output is correct
10 Correct 606 ms 92032 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35672 KB Output is correct
2 Execution timed out 8020 ms 52124 KB Time limit exceeded
3 Halted 0 ms 0 KB -