#include <bits/stdc++.h>
//#pragma GCC optimize ("O2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("strict-overflow")
//#pragma GCC target("avx,avx2,fma")
//#pragma comment(linker, "/STACK:268435456");
#define pb push_back
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
const ll inf = 1e16;
bool blocked[500001];
int n, children[500001], par[500001], cnt[500001], uniRoot;
ll ans = 1e16, dis[500001][19];
vector<pair<int, int>> adj[500001];
gp_hash_table<int, ll> minDis;
void DFS(int u, int prv){
children[u] = 1;
for(auto& i: adj[u]){
if(blocked[i.first] || i.first == prv) continue;
DFS(i.first, u);
children[u] += children[i.first];
}
}
int secDFS(int u, int prv){
bool flag = 1;
for(auto& i: adj[u]) if(! blocked[i.first] && children[i.first]*2 > children[u]) flag = 0;
if(flag) return u;
int anc = -1;
for(auto& i: adj[u]){
if(i.first == prv || blocked[i.first]) continue;
children[u] -= children[i.first];
children[i.first] += children[u];
if(anc == -1) anc = secDFS(i.first, u);
children[i.first] -= children[u];
children[u] += children[i.first];
}
return anc;
}
void distDFS(int u, int prv, ll curDis, int root){
dis[u][cnt[u]++] = curDis;
for(auto& i: adj[u]){
if(blocked[i.first] || i.first == prv) continue;
distDFS(i.first, u, curDis+i.second, root);
}
}
int decompose(int u){
DFS(u, -1);
int root = secDFS(u, -1);
distDFS(root, -1, 0, root);
blocked[root] = 1;
for(auto& i: adj[root]) {
if(blocked[i.first]) continue;
int nextRoot = decompose(i.first);
par[nextRoot] = root;
}
return root;
}
void Init(int N, int A[], int B[], int C[]) {
n = N;
for(int i = 0; i < N-1; i++){
adj[A[i]].pb(mp(B[i], C[i]));
adj[B[i]].pb(mp(A[i], C[i]));
}
uniRoot = decompose(0);
par[uniRoot] = -1;
}
ll Query(int S, int X[], int T, int Y[]){
//The answer is the lowest LCA for a pair {X_i, Y_j} in the Centroid Tree
//O(STlogN) Naive
//How do we process queries in O((S+T)) or O((S+T)logN)?
//Idea: for all S, update the shortest distance for all nodes between the root of the centroid tree and X_i, and for Y_i, move up the centroid tree and update the answer for each node.
//The height of the centroid tree is O(logN), so we get O((S+T)logN)
//We can use Euler Tour Trick to get distances in O(1)
//Alternatively just store the distances
ans = inf;
minDis.clear();
for(int i = 0; i < S; i++){
int cur = X[i], curcnt = cnt[X[i]]-1;
while(cur != -1){
if(minDis.find(cur) == minDis.end()) minDis[cur] = inf;
minDis[cur] = min(minDis[cur], dis[X[i]][curcnt--]);
cur = par[cur];
}
}
for(int i = 0; i < T; i++){
int cur = Y[i], curcnt = cnt[Y[i]]-1;
while(cur != -1){
if(minDis.find(cur) != minDis.end()) ans = min(ans, minDis[cur]+dis[Y[i]][curcnt]);
curcnt--;
cur = par[cur];
}
}
assert(ans != 0);
return ans;
}
/*
int main() {
cin.sync_with_stdio(NULL);
cin.tie(NULL);
int A[6] = {0, 1, 2, 2, 4, 1}, B[6] = {1, 2, 3, 4, 5, 6}, C[6] = {4, 4, 5, 6, 5, 3};
Init(7, A, B, C);
int X1[2] = {0, 6}, Y1[2] = {3, 4};
cout << Query(2, X1, 2, Y1) << "\n";
int X2[3] = {0, 1, 3}, Y2[2] = {4, 6};
cout << Query(3, X2, 2, Y2) << "\n";
int X3[1] = {2}, Y3[1] = {5};
cout << Query(1, X3, 1, Y3) << "\n";
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
12372 KB |
Output is correct |
2 |
Correct |
422 ms |
21436 KB |
Output is correct |
3 |
Correct |
559 ms |
21288 KB |
Output is correct |
4 |
Correct |
429 ms |
21840 KB |
Output is correct |
5 |
Correct |
525 ms |
21668 KB |
Output is correct |
6 |
Correct |
242 ms |
21248 KB |
Output is correct |
7 |
Correct |
549 ms |
21128 KB |
Output is correct |
8 |
Correct |
584 ms |
21292 KB |
Output is correct |
9 |
Correct |
564 ms |
21664 KB |
Output is correct |
10 |
Correct |
249 ms |
21240 KB |
Output is correct |
11 |
Correct |
555 ms |
21188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12244 KB |
Output is correct |
2 |
Correct |
1948 ms |
124312 KB |
Output is correct |
3 |
Correct |
3086 ms |
125708 KB |
Output is correct |
4 |
Correct |
678 ms |
124972 KB |
Output is correct |
5 |
Correct |
3990 ms |
148308 KB |
Output is correct |
6 |
Correct |
3728 ms |
127440 KB |
Output is correct |
7 |
Correct |
1476 ms |
42932 KB |
Output is correct |
8 |
Correct |
458 ms |
43712 KB |
Output is correct |
9 |
Correct |
1792 ms |
47108 KB |
Output is correct |
10 |
Correct |
1531 ms |
44376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
12372 KB |
Output is correct |
2 |
Correct |
422 ms |
21436 KB |
Output is correct |
3 |
Correct |
559 ms |
21288 KB |
Output is correct |
4 |
Correct |
429 ms |
21840 KB |
Output is correct |
5 |
Correct |
525 ms |
21668 KB |
Output is correct |
6 |
Correct |
242 ms |
21248 KB |
Output is correct |
7 |
Correct |
549 ms |
21128 KB |
Output is correct |
8 |
Correct |
584 ms |
21292 KB |
Output is correct |
9 |
Correct |
564 ms |
21664 KB |
Output is correct |
10 |
Correct |
249 ms |
21240 KB |
Output is correct |
11 |
Correct |
555 ms |
21188 KB |
Output is correct |
12 |
Correct |
9 ms |
12244 KB |
Output is correct |
13 |
Correct |
1948 ms |
124312 KB |
Output is correct |
14 |
Correct |
3086 ms |
125708 KB |
Output is correct |
15 |
Correct |
678 ms |
124972 KB |
Output is correct |
16 |
Correct |
3990 ms |
148308 KB |
Output is correct |
17 |
Correct |
3728 ms |
127440 KB |
Output is correct |
18 |
Correct |
1476 ms |
42932 KB |
Output is correct |
19 |
Correct |
458 ms |
43712 KB |
Output is correct |
20 |
Correct |
1792 ms |
47108 KB |
Output is correct |
21 |
Correct |
1531 ms |
44376 KB |
Output is correct |
22 |
Correct |
2210 ms |
138040 KB |
Output is correct |
23 |
Correct |
2356 ms |
151444 KB |
Output is correct |
24 |
Correct |
3426 ms |
139400 KB |
Output is correct |
25 |
Correct |
3653 ms |
168080 KB |
Output is correct |
26 |
Correct |
3569 ms |
152788 KB |
Output is correct |
27 |
Correct |
4804 ms |
195408 KB |
Output is correct |
28 |
Correct |
886 ms |
159760 KB |
Output is correct |
29 |
Correct |
3547 ms |
152096 KB |
Output is correct |
30 |
Correct |
3627 ms |
151768 KB |
Output is correct |
31 |
Correct |
3751 ms |
152320 KB |
Output is correct |
32 |
Correct |
1353 ms |
73536 KB |
Output is correct |
33 |
Correct |
458 ms |
63880 KB |
Output is correct |
34 |
Correct |
935 ms |
55300 KB |
Output is correct |
35 |
Correct |
904 ms |
55008 KB |
Output is correct |
36 |
Correct |
1153 ms |
55488 KB |
Output is correct |
37 |
Correct |
1216 ms |
55500 KB |
Output is correct |