#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <int, ll>
#define pb push_back
#define ff first
#define ss second
const int N = 5e5+5;
const ll inf = 1e18;
int rem[N], sub[N], par[N], sp[N][20], lvl[N];
ll w[N], cur[N];
vector<pii> E[N];
// void dfs(int nd, int pr){
// sub[nd] = 1;
// for (auto i : E[nd]){
// if (i.ff == pr or rem[i.ff]) continue;
// dfs(i.ff, nd);
// sub[nd] += sub[i.ff];
// }
// }
// int centroid(int nd, int pr, int sz){
// for (auto i : E[nd]){
// if (i.ff == pr or rem[i.ff]) continue;
// if (sub[i.ff]*2 > sz) return centroid(i.ff, nd, sz);
// }
// return nd;
// }
// void build(int nd, int pr){
// int centr = centroid(nd, 0, sub[nd]);
// rem[centr] = 1;
// par[centr] = pr;
// for (auto i : E[centr]){
// if (!rem[i.ff]){
// dfs(i.ff, 0);
// build(i.ff, centr);
// }
// }
// }
void dfs2(int nd, int pr){
sp[nd][0] = pr;
for (auto i : E[nd]){
if (i.ff == pr) continue;
lvl[i.ff] = lvl[nd]+1;
w[i.ff] = w[nd]+i.ss;
dfs2(i.ff, nd);
}
}
int LCA(int u, int v){
if (lvl[u] < lvl[v]) swap(u, v);
int diff = lvl[u]-lvl[v];
for (int i = 19; i >= 0; i--){
if (diff&(1<<i)) u = sp[u][i];
}
if (u == v) return v;
for (int i = 19; i >= 0; i--){
if (sp[u][i] != sp[v][i]){
u = sp[u][i];
v = sp[v][i];
}
}
return sp[u][0];
}
ll dist(int u, int v){
if (u == v) return 0ll;
return w[u]+w[v]-2*w[LCA(u,v)];
}
void Init(int n, int A[], int B[], int D[]){
for (int i = 0; i < n-1; i++){
A[i]++;
B[i]++;
E[A[i]].pb({B[i], D[i]});
E[B[i]].pb({A[i], D[i]});
}
// dfs(1, 0);
// build(1, 0);
dfs2(1, 0);
for (int j = 1; j <= 19; j++){
for (int i = 1; i <= n; i++) sp[i][j] = sp[sp[i][j-1]][j-1];
}
for (int i = 1; i <= n; i++) cur[i] = inf;
}
// void remv(int nd){
// while(nd){
// cur[nd] = inf;
// nd = par[nd];
// }
// }
// void paint(int nd){
// int u = nd;
// while(u){
// cur[u] = min(cur[u], dist(u, nd));
// u = par[u];
// }
// }
// ll find(int nd){
// ll mn = inf;
// int u = nd;
// while(u){
// mn = min(mn, dist(u, nd)+cur[u]);
// u = par[u];
// }
// return mn;
// }
ll Query(int S, int X[], int T, int Y[]){
for (int i = 0; i < S; i++){
X[i]++;
// paint(X[i]);
}
ll ans = inf;
for (int i = 0; i < T; i++){
Y[i]++;
// ans = min(ans, find(Y[i]));
for (int j = 0; j < S; j++){
ans = min(ans, dist(X[j], Y[i]));
}
}
// for (int i = 0; i < S; i++) remv(X[i]);
return ans;
}
// int main ()
// {
// int n, q;
// cin >> n >> q;
// int A[n], B[n], D[n];
// for (int i = 0; i < n-1; i++){
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(n, A, B, D);
// for (int i = 0; i < q; i++){
// int S, T;
// cin >> S >> T;
// int X[S], Y[T];
// for (int j = 0; j < S; j++) cin >> X[j];
// for (int j = 0; j < T; j++) cin >> Y[j];
// cout << Query(S, X, T, Y) << '\n';
// }
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
12416 KB |
Output is correct |
| 2 |
Execution timed out |
8044 ms |
30188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12244 KB |
Output is correct |
| 2 |
Correct |
1217 ms |
118032 KB |
Output is correct |
| 3 |
Correct |
2342 ms |
120248 KB |
Output is correct |
| 4 |
Correct |
783 ms |
115300 KB |
Output is correct |
| 5 |
Correct |
2591 ms |
145012 KB |
Output is correct |
| 6 |
Correct |
2013 ms |
122432 KB |
Output is correct |
| 7 |
Correct |
3363 ms |
51988 KB |
Output is correct |
| 8 |
Correct |
731 ms |
51900 KB |
Output is correct |
| 9 |
Correct |
2477 ms |
56032 KB |
Output is correct |
| 10 |
Correct |
2067 ms |
53548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
121 ms |
12416 KB |
Output is correct |
| 2 |
Execution timed out |
8044 ms |
30188 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
