#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T> struct RMQ { // floor(log_2(x))
int level(int x) { return 31-__builtin_clz(x); }
vector<T> v; vector<vi> jmp;
int comb(int a, int b) { // index of min
return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); }
void init(const vector<T>& _v) {
v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
for (int j = 1; 1<<j <= sz(v); ++j) {
jmp.pb(vi(sz(v)-(1<<j)+1));
rep(i,0,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
jmp[j-1][i+(1<<(j-1))]);
}
}
int index(int l, int r) { // get index of min element
int d = level(r-l+1);
return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
T query(int l, int r) { return v[index(l,r)]; }
};
struct Tree{
int n;
vector<vector<pii> > g;
vi pos,tin,tout,vis,tam,del,pai;
vector<ll> H,best;
vector<pii> temp;
Tree(){}
int T;
int MY_ROOT = 1;
vi ans[21];
void init(int _n){
T=0;
n = _n;
g.resize(n+1);
best = H = vector<ll>(n+1);
pai = del = vis = tam = pos = tin = tout = vi(n+1);
rep(i,0,20)ans[i].resize(n+1);
}
RMQ<pii> rmq;
void addEdge(int a,int b,int c){
g[a].pb(pii(b,c));
g[b].pb(pii(a,c));
}
void dfs(int v,int p = -1){
pos[v] = sz(temp);
tin[v] = ++T;
temp.pb(pii(H[v],v));
trav(to,g[v])if(to.ff!=p){
H[to.ff] = H[v] + to.ss;
ans[0][to.ff] = v;
dfs(to.ff,v);
temp.pb(pii(H[v],v));
}
tout[v] = T;
}
void gen(int Root){
MY_ROOT = Root;
ans[0][Root] = Root;
dfs(Root);
rmq.init(temp);
rep(j,1,20){
rep(i,0,n+1){
ans[j][i] = ans[j-1][ans[j-1][i]];
}
}
decompose(Root);
}
int lca(int a,int b){
a = pos[a],b = pos[b];
if(a > b)swap(a,b);
return rmq.query(a,b).ss;
}
ll dist(int a,int b){
return H[a] + H[b] - 2*H[lca(a,b)];
}
int calc_sz(int v,int p = -1){
tam[v] = 1;
for(auto to : g[v])if(to.ff!=p and !del[to.ff]){
tam[v]+=calc_sz(to.ff,v);
}
return tam[v];
}
int find_centroid(int v,int p,int Sz){
for(auto to : g[v])if(to.ff!=p and !del[to.ff]){
if(tam[to.ff]*2 > Sz)return find_centroid(to.ff,v,Sz);
}
return v;
}
void decompose(int v,int p = -1){
int Sz = calc_sz(v,-1);
int cent = find_centroid(v,-1,Sz);
pai[cent] = p;
del[cent] = 1;
for(auto to : g[cent]){
if(del[to.ff])continue;
decompose(to.ff,cent);
}
}
int CT = 0;
const ll inf = 1e18;
void add(int x){
int c = x;
while(c!=-1){
if(vis[c] != CT){
vis[c] = CT;best[c] = inf;
}
best[c] = min(best[c],dist(x,c));
c = pai[c];
}
}
ll query(int x){
ll res = inf;
int c = x;
while(c!=-1){
if(vis[c] == CT){
res = min(res,best[c] + dist(x,c));
}
c = pai[c];
}
return res;
}
}tree;
void Init(int N, int A[], int B[], int D[]) {
tree.init(N);
for(int i=0;i<N-1;i++){
tree.addEdge(A[i],B[i],D[i]);
}
tree.gen(0);
}
long long Query(int S, int X[], int T, int Y[]) {
tree.CT++;
for(int i=0;i<S;i++)tree.add(X[i]);
ll res = tree.inf;
for(int i=0;i<T;i++)res = min(res,tree.query(Y[i]));
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
896 KB |
Output is correct |
| 2 |
Correct |
569 ms |
19580 KB |
Output is correct |
| 3 |
Incorrect |
737 ms |
19668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2781 ms |
212952 KB |
Output is correct |
| 3 |
Incorrect |
3657 ms |
215896 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
896 KB |
Output is correct |
| 2 |
Correct |
569 ms |
19580 KB |
Output is correct |
| 3 |
Incorrect |
737 ms |
19668 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
