#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 5e5;
vector<pair<int, long long>> adj[N];
int n, m;
vector<int> euler, depth;
int first[N], last[N], l2[N * 2], p2[N * 2];
long long dep[N];
int sparse[N * 2][22];
int c = 0;
int sub[N], par[N];
long long ans[N];
bool isCen[N];
int size = 0;
// LCA begins
void pre(int v, int p = -1, long long d = 0, int de = 0) {
first[v] = c++;
dep[v] = d;
euler.push_back(v);
depth.push_back(de);
for (auto i : adj[v]) {
if (i.first != p) {
pre(i.first, v, d + i.second, de + 1);
euler.push_back(v);
depth.push_back(de);
c++;
}
}
last[v] = c - 1;
}
int merge(int a, int b) {
return depth[a] < depth[b] ? a : b;
}
void build_sparse() {
int es = n * 2 - 1;
assert(es < N * 2);
assert(l2[es] <= 22);
for (int i = 0; i < es; i++)
sparse[i][0] = i;
for (int i = 1; i <= l2[es]; i++) {
for (int j = 0; j < es && j - 1 + (p2[i]) < es; j++)
sparse[j][i] = depth[sparse[j][i - 1]] < depth[sparse[j + (p2[i - 1])][i - 1]] ? sparse[j][i - 1] : sparse[j + (p2[i - 1])][i - 1];
}
}
int lca(int u, int v) {
if (u == v) return u;
int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1;
int dx = l2[diff];
return euler[merge(sparse[f1][dx], sparse[f2 - (p2[dx])][dx])];
}
long long dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
// LCA ends
// Centroid decomposition begins
void calc(int v, int p = -1) { // Pre calculate subtree sizes
sub[v] = 1;
size++;
for (auto i : adj[v]) {
if (i.first != p && !isCen[i.first])
calc(i.first, v), sub[v] += sub[i.first];
}
}
int find(int v, int p = -1) { // Find the centroid in current subtree
for (auto i : adj[v]) {
if (i.first != p && !isCen[i.first] && sub[i.first] > size / 2)
return find(i.first, v);
}
return v;
}
void decompose(int v, int p = -1) {
size = 0; // Stores size of current subtree
calc(v);
int centroid = find(v);
par[centroid] = p;
isCen[centroid] = true;
for (auto i : adj[centroid]) {
if (i.first != p && !isCen[i.first])
decompose(i.first, centroid);
}
}
// Centroid decomposition ends
void update(int v) {
int p = v, co = 0;
while (p != -1) {
ans[p] = min(ans[p], dist(p, v));
p = par[p];
}
assert(co <= 22);
}
long long query(int v) {
int p = v, co = 0;
long long val = 1e18;
while (p != -1) {
val = min(val, ans[p] + dist(p, v));
p = par[p];
}
assert(co <= 22);
return val;
}
void revert(int v) {
int p = v;
while (p != -1) {
ans[p] = 1e18;
p = par[p];
}
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++)
update(X[i]);
long long ans = 1e18;
for (int i = 0; i < T; i++)
ans = min(ans, query(Y[i]));
for (int i = 0; i < S; i++)
revert(X[i]);
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n - 1; i++) {
adj[A[i]].emplace_back(B[i], D[i]);
adj[B[i]].emplace_back(A[i], D[i]);
}
p2[0] = 1;
for (int i=1; i<30; i++)
p2[i] = p2[i-1]*2;
// memorizing all log(n) values
int val = 1,ptr=0;
for (int i=1; i<n * 2; i++)
{
l2[i] = ptr-1;
if (val==i)
{
val*=2;
l2[i] = ptr;
ptr++;
}
}
pre(0);
build_sparse();
decompose(0);
fill(ans, ans + N, 1e18);
}
Compilation message
factories.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
factories.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
12544 KB |
Output is correct |
2 |
Correct |
488 ms |
21752 KB |
Output is correct |
3 |
Correct |
581 ms |
21752 KB |
Output is correct |
4 |
Correct |
580 ms |
21924 KB |
Output is correct |
5 |
Correct |
663 ms |
22008 KB |
Output is correct |
6 |
Correct |
340 ms |
21772 KB |
Output is correct |
7 |
Correct |
579 ms |
21880 KB |
Output is correct |
8 |
Correct |
582 ms |
21752 KB |
Output is correct |
9 |
Correct |
653 ms |
21980 KB |
Output is correct |
10 |
Correct |
340 ms |
21752 KB |
Output is correct |
11 |
Correct |
571 ms |
21752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
12416 KB |
Output is correct |
2 |
Correct |
2697 ms |
164780 KB |
Output is correct |
3 |
Correct |
3746 ms |
166928 KB |
Output is correct |
4 |
Correct |
1150 ms |
167780 KB |
Output is correct |
5 |
Correct |
4559 ms |
186140 KB |
Output is correct |
6 |
Correct |
3891 ms |
168480 KB |
Output is correct |
7 |
Correct |
1982 ms |
51556 KB |
Output is correct |
8 |
Correct |
646 ms |
52672 KB |
Output is correct |
9 |
Correct |
2065 ms |
54712 KB |
Output is correct |
10 |
Correct |
2074 ms |
53108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
12544 KB |
Output is correct |
2 |
Correct |
488 ms |
21752 KB |
Output is correct |
3 |
Correct |
581 ms |
21752 KB |
Output is correct |
4 |
Correct |
580 ms |
21924 KB |
Output is correct |
5 |
Correct |
663 ms |
22008 KB |
Output is correct |
6 |
Correct |
340 ms |
21772 KB |
Output is correct |
7 |
Correct |
579 ms |
21880 KB |
Output is correct |
8 |
Correct |
582 ms |
21752 KB |
Output is correct |
9 |
Correct |
653 ms |
21980 KB |
Output is correct |
10 |
Correct |
340 ms |
21752 KB |
Output is correct |
11 |
Correct |
571 ms |
21752 KB |
Output is correct |
12 |
Correct |
13 ms |
12416 KB |
Output is correct |
13 |
Correct |
2697 ms |
164780 KB |
Output is correct |
14 |
Correct |
3746 ms |
166928 KB |
Output is correct |
15 |
Correct |
1150 ms |
167780 KB |
Output is correct |
16 |
Correct |
4559 ms |
186140 KB |
Output is correct |
17 |
Correct |
3891 ms |
168480 KB |
Output is correct |
18 |
Correct |
1982 ms |
51556 KB |
Output is correct |
19 |
Correct |
646 ms |
52672 KB |
Output is correct |
20 |
Correct |
2065 ms |
54712 KB |
Output is correct |
21 |
Correct |
2074 ms |
53108 KB |
Output is correct |
22 |
Correct |
3740 ms |
166796 KB |
Output is correct |
23 |
Correct |
3894 ms |
169008 KB |
Output is correct |
24 |
Correct |
5483 ms |
169324 KB |
Output is correct |
25 |
Correct |
5499 ms |
172740 KB |
Output is correct |
26 |
Correct |
5557 ms |
169564 KB |
Output is correct |
27 |
Correct |
6181 ms |
185620 KB |
Output is correct |
28 |
Correct |
1500 ms |
171912 KB |
Output is correct |
29 |
Correct |
5488 ms |
169136 KB |
Output is correct |
30 |
Correct |
5414 ms |
168968 KB |
Output is correct |
31 |
Correct |
5679 ms |
169416 KB |
Output is correct |
32 |
Correct |
2196 ms |
55884 KB |
Output is correct |
33 |
Correct |
681 ms |
53220 KB |
Output is correct |
34 |
Correct |
1486 ms |
49764 KB |
Output is correct |
35 |
Correct |
1538 ms |
49948 KB |
Output is correct |
36 |
Correct |
1997 ms |
50324 KB |
Output is correct |
37 |
Correct |
2021 ms |
50580 KB |
Output is correct |