#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define int long long
#define sz(x) (int)x.size()
#define i32 int32_t
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
const int MAXN = 5e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
vector<pii> edges[MAXN];
int ver[MAXN][20], cen[MAXN][20], cc, sz[MAXN];
int used[MAXN], d[MAXN], n;
void dfs(int u, int p, int j, int d = 0){
ver[u][j] = d, cen[u][j] = cc, sz[u] = 1;
for(auto x : edges[u]){
if(used[x.ff] || p == x.ff) continue;
dfs(x.ff, u, j, d+x.ss), sz[u] += sz[x.ff];
}
}
int centr(int u, int p = -1){
for(auto x : edges[u]){
if(x.ff == p || used[x.ff]) continue;
if(sz[x.ff] > n / 2) return centr(x.ff, u);
} return u;
}
void cdec(int u, int j = 0){
dfs(u, -1, j), n = sz[u];
cc = centr(u);
//~ cout<<cc<<"\n";
dfs(cc, -1, j);
used[cc] = 1;
for(auto x : edges[cc]){
if(used[x.ff]) continue;
cdec(x.ff, j+1);
}
}
void Init(i32 N, i32 a[], i32 b[], i32 D[]) {
n = N;
for(int i=0;i<n-1;i++){ a[i]++, b[i]++;
edges[a[i]].pb({b[i], D[i]}), edges[b[i]].pb({a[i], D[i]});
}
cdec(1);
n = N;
for(int i=1;i<=N;i++) d[i] = inf;
}
int Query(i32 s, i32 x[], i32 t, i32 y[]) {
for(int i=0;i<s;i++) x[i]++;
for(int i=0;i<t;i++) y[i]++;
int res = inf;
for(int i=0;i<s;i++)
for(int j=0;j<20;j++) if(cen[x[i]][j]) umin(d[cen[x[i]][j]], ver[x[i]][j]);
for(int i=0;i<t;i++)
for(int j=0;j<20;j++) if(cen[y[i]][j]) umin(res, d[cen[y[i]][j]] + ver[y[i]][j]);
for(int i=0;i<s;i++)
for(int j=0;j<20;j++) if(cen[x[i]][j]) d[cen[x[i]][j]] = inf;
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
12492 KB |
Output is correct |
2 |
Correct |
399 ms |
22004 KB |
Output is correct |
3 |
Correct |
423 ms |
22084 KB |
Output is correct |
4 |
Correct |
405 ms |
22120 KB |
Output is correct |
5 |
Correct |
417 ms |
22436 KB |
Output is correct |
6 |
Correct |
353 ms |
22156 KB |
Output is correct |
7 |
Correct |
403 ms |
22136 KB |
Output is correct |
8 |
Correct |
413 ms |
22068 KB |
Output is correct |
9 |
Correct |
421 ms |
22436 KB |
Output is correct |
10 |
Correct |
400 ms |
22028 KB |
Output is correct |
11 |
Correct |
409 ms |
22080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12364 KB |
Output is correct |
2 |
Correct |
2378 ms |
218804 KB |
Output is correct |
3 |
Correct |
3540 ms |
222652 KB |
Output is correct |
4 |
Correct |
1086 ms |
216660 KB |
Output is correct |
5 |
Correct |
4505 ms |
253012 KB |
Output is correct |
6 |
Correct |
3629 ms |
223928 KB |
Output is correct |
7 |
Correct |
1068 ms |
62224 KB |
Output is correct |
8 |
Correct |
793 ms |
61980 KB |
Output is correct |
9 |
Correct |
1178 ms |
66812 KB |
Output is correct |
10 |
Correct |
1068 ms |
63484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
12492 KB |
Output is correct |
2 |
Correct |
399 ms |
22004 KB |
Output is correct |
3 |
Correct |
423 ms |
22084 KB |
Output is correct |
4 |
Correct |
405 ms |
22120 KB |
Output is correct |
5 |
Correct |
417 ms |
22436 KB |
Output is correct |
6 |
Correct |
353 ms |
22156 KB |
Output is correct |
7 |
Correct |
403 ms |
22136 KB |
Output is correct |
8 |
Correct |
413 ms |
22068 KB |
Output is correct |
9 |
Correct |
421 ms |
22436 KB |
Output is correct |
10 |
Correct |
400 ms |
22028 KB |
Output is correct |
11 |
Correct |
409 ms |
22080 KB |
Output is correct |
12 |
Correct |
9 ms |
12364 KB |
Output is correct |
13 |
Correct |
2378 ms |
218804 KB |
Output is correct |
14 |
Correct |
3540 ms |
222652 KB |
Output is correct |
15 |
Correct |
1086 ms |
216660 KB |
Output is correct |
16 |
Correct |
4505 ms |
253012 KB |
Output is correct |
17 |
Correct |
3629 ms |
223928 KB |
Output is correct |
18 |
Correct |
1068 ms |
62224 KB |
Output is correct |
19 |
Correct |
793 ms |
61980 KB |
Output is correct |
20 |
Correct |
1178 ms |
66812 KB |
Output is correct |
21 |
Correct |
1068 ms |
63484 KB |
Output is correct |
22 |
Correct |
2705 ms |
220360 KB |
Output is correct |
23 |
Correct |
2827 ms |
222572 KB |
Output is correct |
24 |
Correct |
4002 ms |
224352 KB |
Output is correct |
25 |
Correct |
4083 ms |
227916 KB |
Output is correct |
26 |
Correct |
3894 ms |
224628 KB |
Output is correct |
27 |
Correct |
4930 ms |
249860 KB |
Output is correct |
28 |
Correct |
1524 ms |
220452 KB |
Output is correct |
29 |
Correct |
3896 ms |
224108 KB |
Output is correct |
30 |
Correct |
3839 ms |
223508 KB |
Output is correct |
31 |
Correct |
3898 ms |
224224 KB |
Output is correct |
32 |
Correct |
1293 ms |
67864 KB |
Output is correct |
33 |
Correct |
829 ms |
62308 KB |
Output is correct |
34 |
Correct |
915 ms |
59844 KB |
Output is correct |
35 |
Correct |
939 ms |
59948 KB |
Output is correct |
36 |
Correct |
1102 ms |
60912 KB |
Output is correct |
37 |
Correct |
1093 ms |
61020 KB |
Output is correct |