#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 5e5 + 2;
const ll INF = 1e18;
int lg[N * 4];
int n, sz[N], mx[N], block[N], cent_pr[N], depth[N], ord[21][N * 4], timer, tin[N];
ll dp[N], mcost[N];
int last_used[N], Q;
vector< pair< int, int > > g[N];
void dfs_sz(int v, int pr){
sz[v] = 1, mx[v] = 0;
for(pair<int, int> to: g[v]){
if(to.X == pr || block[to.X])
continue;
dfs_sz(to.X, v), sz[v] += sz[to.X];
mx[v] = (sz[mx[v]] < sz[to.X] ? to.X: mx[v]);
}
}
int get_cent(int v){
int u = v;
while(sz[mx[u]] * 2 > sz[v])
u = mx[u];
return u;
}
void cent(int v, int pr){
dfs_sz(v, v), v = get_cent(v);
cent_pr[v] = pr, block[v] = 1;
for(pair<int, int> to: g[v]){
if(!block[to.X])
cent(to.X, v);
}
}
void dfs_prep(int v, int pr){
tin[v] = ++timer, ord[0][timer] = v;
for(pair<int, int> to: g[v]){
if(to.X == pr)
continue;
dp[to.X] = dp[v] + to.Y, depth[to.X] = depth[v] + 1;
dfs_prep(to.X, v);
ord[0][++timer] = v;
}
}
ll calc(int x, int y){
if(tin[x] > tin[y])
swap(x, y);
int mid = (tin[y] - tin[x] + 1);
mid = (depth[ord[lg[mid]][tin[x]]] < depth[ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]] ? ord[lg[mid]][tin[x]]: ord[lg[mid]][tin[y] - (1 << lg[mid]) + 1]);
// cerr << x - 1 << " " << y - 1 << " " << mid - 1 << "\n";
return dp[x] + dp[y] - 2 * dp[mid];
}
void Init(int N2, int A[], int B[], int D[]) {
for(int i = 2;i < N * 4;i++)
lg[i] = lg[i / 2] + 1;
n = N2;
for(int i = 0;i < n - 1;i++){
g[A[i] + 1].push_back(MP(B[i] + 1, D[i]));
g[B[i] + 1].push_back(MP(A[i] + 1, D[i]));
}
cent(1, 0);
dfs_prep(1, 1);
for(int i = 1;i <= 20;i++)
for(int j = 1;j + (1 << i) - 1 <= timer;j++)
ord[i][j] = (depth[ord[i - 1][j]] < depth[ord[i - 1][j + (1 << (i - 1))]] ? ord[i - 1][j]: ord[i - 1][j + (1 << (i - 1))]);
}
long long Query(int S, int X[], int T, int Y[]) {
// cerr << "NEXT\n";
ll ans = INF;
Q++;
for(int i = 0;i < S;i++){
X[i]++;
int j = X[i];
while(j){
if(last_used[j] != Q)
last_used[j] = Q, mcost[j] = INF;
mcost[j] = min(mcost[j], calc(j, X[i]));
// cerr << j - 1 << " " << X[i - 1] << " " << calc(j, X[i]) << "\n";
j = cent_pr[j];
}
}
for(int i = 0;i < T;i++){
Y[i]++;
int j = Y[i];
while(j){
if(last_used[j] != Q)
last_used[j] = Q, mcost[j] = INF;
ans = min(ans, mcost[j] + calc(j, Y[i]));
// cerr << j - 1 << " " << Y[i] - 1 << " " << ans << " " << mcost[j] << " " << calc(j, Y[i]) << "\n";
j = cent_pr[j];
}
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
20716 KB |
Output is correct |
2 |
Correct |
523 ms |
38508 KB |
Output is correct |
3 |
Correct |
740 ms |
38560 KB |
Output is correct |
4 |
Correct |
686 ms |
38660 KB |
Output is correct |
5 |
Correct |
687 ms |
38892 KB |
Output is correct |
6 |
Correct |
317 ms |
38636 KB |
Output is correct |
7 |
Correct |
701 ms |
38632 KB |
Output is correct |
8 |
Correct |
696 ms |
38632 KB |
Output is correct |
9 |
Correct |
697 ms |
38944 KB |
Output is correct |
10 |
Correct |
370 ms |
38560 KB |
Output is correct |
11 |
Correct |
687 ms |
38572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
20332 KB |
Output is correct |
2 |
Correct |
3054 ms |
165928 KB |
Output is correct |
3 |
Correct |
4436 ms |
167668 KB |
Output is correct |
4 |
Correct |
1109 ms |
166320 KB |
Output is correct |
5 |
Correct |
5593 ms |
196844 KB |
Output is correct |
6 |
Correct |
4700 ms |
169836 KB |
Output is correct |
7 |
Correct |
2666 ms |
66280 KB |
Output is correct |
8 |
Correct |
638 ms |
66912 KB |
Output is correct |
9 |
Correct |
2809 ms |
70752 KB |
Output is correct |
10 |
Correct |
2613 ms |
67692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
20716 KB |
Output is correct |
2 |
Correct |
523 ms |
38508 KB |
Output is correct |
3 |
Correct |
740 ms |
38560 KB |
Output is correct |
4 |
Correct |
686 ms |
38660 KB |
Output is correct |
5 |
Correct |
687 ms |
38892 KB |
Output is correct |
6 |
Correct |
317 ms |
38636 KB |
Output is correct |
7 |
Correct |
701 ms |
38632 KB |
Output is correct |
8 |
Correct |
696 ms |
38632 KB |
Output is correct |
9 |
Correct |
697 ms |
38944 KB |
Output is correct |
10 |
Correct |
370 ms |
38560 KB |
Output is correct |
11 |
Correct |
687 ms |
38572 KB |
Output is correct |
12 |
Correct |
18 ms |
20332 KB |
Output is correct |
13 |
Correct |
3054 ms |
165928 KB |
Output is correct |
14 |
Correct |
4436 ms |
167668 KB |
Output is correct |
15 |
Correct |
1109 ms |
166320 KB |
Output is correct |
16 |
Correct |
5593 ms |
196844 KB |
Output is correct |
17 |
Correct |
4700 ms |
169836 KB |
Output is correct |
18 |
Correct |
2666 ms |
66280 KB |
Output is correct |
19 |
Correct |
638 ms |
66912 KB |
Output is correct |
20 |
Correct |
2809 ms |
70752 KB |
Output is correct |
21 |
Correct |
2613 ms |
67692 KB |
Output is correct |
22 |
Correct |
4360 ms |
153836 KB |
Output is correct |
23 |
Correct |
4508 ms |
176000 KB |
Output is correct |
24 |
Correct |
6641 ms |
175848 KB |
Output is correct |
25 |
Correct |
6472 ms |
179424 KB |
Output is correct |
26 |
Correct |
6678 ms |
175852 KB |
Output is correct |
27 |
Correct |
7708 ms |
199508 KB |
Output is correct |
28 |
Correct |
1439 ms |
176772 KB |
Output is correct |
29 |
Correct |
6787 ms |
175536 KB |
Output is correct |
30 |
Correct |
6731 ms |
174856 KB |
Output is correct |
31 |
Correct |
6656 ms |
175596 KB |
Output is correct |
32 |
Correct |
2751 ms |
71692 KB |
Output is correct |
33 |
Correct |
602 ms |
67424 KB |
Output is correct |
34 |
Correct |
1830 ms |
64108 KB |
Output is correct |
35 |
Correct |
1886 ms |
63980 KB |
Output is correct |
36 |
Correct |
2457 ms |
64596 KB |
Output is correct |
37 |
Correct |
2572 ms |
64752 KB |
Output is correct |