oj.uz

Submission #1031800

# Submission time Handle Problem Language Result Execution time Memory
1031800 2024-07-23T07:27:20 Z juicy Factories (JOI14_factories) C++17
100 / 100
 2793 ms 184196 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
 
const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;
 
int ord[mxN], sz[mxN], pr[mxN], spt[LG][2 * mxN];
long long dep[mxN], mn[mxN];
bool del[mxN];
vector<pair<int, int>> g[mxN];
 
int timer = 0;
 
void pre_dfs(int u) {
	spt[0][ord[u] = ++timer] = u;
	for (auto [v, w] : g[u]) {
		if (!ord[v]) {
			dep[v] = dep[u] + w;
			pre_dfs(v);
			spt[0][++timer] = u;
		}
	}
}
 
int mint(int u, int v) {
	return ord[u] < ord[v] ? u : v;
}
 
int lca(int u, int v) {
	int l = ord[u], r = ord[v];
	if (l > r) {
		swap(l, r);
	}
	int k = __lg(r - l + 1);
	return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}
 
long long dis(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
 
void dfs(int u, int p) {
	sz[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}
 
int findCen(int u, int p, int tot) {
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p && sz[v] * 2 > tot) {
			return findCen(v, u, tot);
		}
	}
	return u;
}
 
int split(int u) {
	dfs(u, u);
	u = findCen(u, u, sz[u]);
  	del[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v]) {
			pr[split(v)] = u;
		}
	}
  return u;
}
 
void ins(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = min(mn[p], dis(u, p));
	}
}
 
void ers(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = inf;
	}
}
 
long long get(int u) {
	long long ans = inf;
	for (int p = u; p; p = pr[p]) {
		ans = min(ans, mn[p] + dis(p, u));
	}
	return ans;
}
 
void Init(int N, int *A, int *B, int *D) {
	for (int i = 0; i < N - 1; ++i) {
    	++A[i], ++B[i];
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	pre_dfs(1);
	for (int j = 1; j < LG; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
			spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
		}
	}
	split(1);
	fill(mn + 1, mn + N + 1, inf);
}
 
long long Query(int S, int *X, int T, int *Y) {
	for (int i = 0; i < T; ++i) {
		ins(++Y[i]);
	}
	long long res = inf;
	for (int i = 0; i < S; ++i) {
		res = min(res, get(++X[i]));
	}
	for (int i = 0; i < T; ++i) {
		ers(Y[i]);
	}
	return res;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:109:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  109 |    spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12636 KB Output is correct
2 Correct 260 ms 30336 KB Output is correct
3 Correct 333 ms 30184 KB Output is correct
4 Correct 338 ms 30288 KB Output is correct
5 Correct 369 ms 30520 KB Output is correct
6 Correct 204 ms 30396 KB Output is correct
7 Correct 306 ms 30292 KB Output is correct
8 Correct 339 ms 30312 KB Output is correct
9 Correct 381 ms 30584 KB Output is correct
10 Correct 201 ms 30296 KB Output is correct
11 Correct 293 ms 30212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12380 KB Output is correct
2 Correct 1085 ms 149876 KB Output is correct
3 Correct 1411 ms 151448 KB Output is correct
4 Correct 412 ms 150928 KB Output is correct
5 Correct 2186 ms 181588 KB Output is correct
6 Correct 1564 ms 154420 KB Output is correct
7 Correct 734 ms 56896 KB Output is correct
8 Correct 255 ms 57536 KB Output is correct
9 Correct 1000 ms 61264 KB Output is correct
10 Correct 760 ms 58340 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12636 KB Output is correct
2 Correct 260 ms 30336 KB Output is correct
3 Correct 333 ms 30184 KB Output is correct
4 Correct 338 ms 30288 KB Output is correct
5 Correct 369 ms 30520 KB Output is correct
6 Correct 204 ms 30396 KB Output is correct
7 Correct 306 ms 30292 KB Output is correct
8 Correct 339 ms 30312 KB Output is correct
9 Correct 381 ms 30584 KB Output is correct
10 Correct 201 ms 30296 KB Output is correct
11 Correct 293 ms 30212 KB Output is correct
12 Correct 5 ms 12380 KB Output is correct
13 Correct 1085 ms 149876 KB Output is correct
14 Correct 1411 ms 151448 KB Output is correct
15 Correct 412 ms 150928 KB Output is correct
16 Correct 2186 ms 181588 KB Output is correct
17 Correct 1564 ms 154420 KB Output is correct
18 Correct 734 ms 56896 KB Output is correct
19 Correct 255 ms 57536 KB Output is correct
20 Correct 1000 ms 61264 KB Output is correct
21 Correct 760 ms 58340 KB Output is correct
22 Correct 1483 ms 157740 KB Output is correct
23 Correct 1551 ms 160568 KB Output is correct
24 Correct 2131 ms 160420 KB Output is correct
25 Correct 2025 ms 164180 KB Output is correct
26 Correct 2113 ms 160512 KB Output is correct
27 Correct 2793 ms 184196 KB Output is correct
28 Correct 488 ms 161456 KB Output is correct
29 Correct 2056 ms 160028 KB Output is correct
30 Correct 2112 ms 159580 KB Output is correct
31 Correct 2154 ms 160208 KB Output is correct
32 Correct 894 ms 62104 KB Output is correct
33 Correct 244 ms 57816 KB Output is correct
34 Correct 546 ms 54588 KB Output is correct
35 Correct 498 ms 54596 KB Output is correct
36 Correct 785 ms 55044 KB Output is correct
37 Correct 715 ms 55120 KB Output is correct