#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int L = 19;
struct node {
vector<pair<node*,int>> l;
long long d;
int depth;
node* anc[L];
node* par;
long long dpar = 0;
bool v = false;
int sz;
long long cl = LONG_LONG_MAX;
};
node* lca(node* u, node* v){
if(u->depth < v->depth) swap(u, v);
int d = u->depth-v->depth;
for(int i = 0;i < L;i++) if((d>>i)&1) u = u->anc[i];
if(u == v) return u;
for(int i = L-1;i >= 0;i--){
if(u->anc[i] != v->anc[i]) {
u = u->anc[i];
v = v->anc[i];
}
}
return u->anc[0];
}
int tot;
void ffs(node* n, node* p, long long d, int depth){
n->d = d;
n->depth = depth;
n->anc[0] = p;
for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1];
for(auto [c, l] : n->l){
if(c != p) ffs(c, n, d+l, depth+1);
}
}
void dfs(node* n, node* p){
n->sz = 1;
for(auto [c, d] : n->l){
if(c == p || c->v) continue;
dfs(c, n);
n->sz += c->sz;
}
}
node* cent(node* n, node* p){
for(auto [c,d]:n->l){
if(c==p||c->v) continue;
if(c->sz>tot/2){
return cent(c, n);
}
}
n->v = true;
for(auto [c,d] : n->l){
if(c->v) continue;
dfs(c, n);
tot = c->sz;
node* ce = cent(c, n);
ce->par = n;
ce->dpar = n->d+ce->d - 2*lca(n, ce)->d;
}
return n;
}
vector<node> g;
void Init(int N, int A[], int B[], int D[]) {
g.resize(N);
for(int i = 0;i < N-1;i++){
g[A[i]].l.emplace_back(&g[B[i]], D[i]);
g[B[i]].l.emplace_back(&g[A[i]], D[i]);
}
tot = N;
ffs(&g[0], &g[0], 0, 0);
dfs(&g[0], NULL);
cent(&g[0], NULL)->par = NULL;
N = 1;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<node*> t;
for(int i = 0;i < S;i++){
node* x = &g[X[i]];
long long cur = 0;
while(x != NULL){
if(x->cl < cur) break;
t.push_back(x);
x->cl = cur;
cur += x->dpar;
x = x->par;
}
}
long long ans = LONG_LONG_MAX;
for(int i = 0;i < T;i++){
node* y = &g[Y[i]];
long long cur = 0;
while(y != NULL){
if(y->cl != LONG_LONG_MAX) ans = min(ans, cur+y->cl);
cur += y->dpar;
y = y->par;
}
}
for(node* n : t) n->cl = LONG_LONG_MAX;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
16984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
