#include "factories.h"
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'
const ll INF = (1ll * 1e18);
int n;
vector<arr(2)> tr[500000];
int p[500000] , id[500000] , r[500000] , cmp[500000];
ll h[500000] , seg[2][2000001];
int seginf[2000001][2] , is[500000];
vector<arr(2)> bck;
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r , seg[0][i] = INF , seg[1][i] = INF;
if(r > l){
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
}else is[l] = i;
}
void updF(int l , int r , int i , ll val){
if(seginf[i][0] >= l and seginf[i][1] <= r) seg[0][i] = min(seg[0][i] , val) , bck.pb({0 , i});
else if(seginf[i][1] >= l and seginf[i][0] <= r) updF(l , r , i << 1 , val) , updF(l , r , (i << 1) | 1 , val);
}
ll getF(int i){
ll res = seg[0][i];
while(i > 1) i /= 2 , res = min(res , seg[0][i]);
return res;
}
void updPt(int i , ll val){
while(i >= 1) seg[1][i] = min(seg[1][i] , val) , bck.pb({1 , i}) , i /= 2;
}
ll getPt(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[1][i];
if(seginf[i][1] >= l and seginf[i][0] <= r) return min(getPt(l , r , i << 1) , getPt(l , r , (i << 1) | 1));
return INF;
}
void ersSeg(){
for(auto &el : bck) seg[el[0]][el[1]] = INF;
bck.cl();
}
void dfs1(int v = 0){
if(v == 0) p[0] = -1;
cmp[v] = 1;
for(auto d : tr[v]){
int u = d[0] , c = d[1];
if(u == p[v]) continue;
p[u] = v , h[u] = h[v] + (1ll * c);
dfs1(u);
cmp[v] += cmp[u];
}
}
int timer = 0;
void dfs2(int v = 0){
id[v] = timer++;
int u = -1;
for(auto el : tr[v]){
if(el[0] == p[v]) continue;
if(u == -1 or cmp[u] < cmp[el[0]]) u = el[0];
}
if(u == -1) return;
r[u] = r[v] , dfs2(u);
for(auto el : tr[v]){
if(el[0] == p[v] or el[0] == u) continue;
r[el[0]] = el[0] , dfs2(el[0]);
}
}
void Init(int N , int A[] , int B[] , int D[]){
n = N;
for(int i = 0 ; i < n - 1 ; i++) tr[A[i]].pb({B[i] , D[i]}) , tr[B[i]].pb({A[i] , D[i]});
dfs1() , dfs2() , buildSeg();
}
ll Query(int S , int X[] , int T , int Y[]){
for(int i = 0 ; i < T ; i++){
int v = Y[i] , cur = v;
while(cur != -1){
updF(id[r[cur]] , id[cur] , 1 , h[v]);
updPt(is[id[cur]] , h[v] - h[cur]);
cur = p[r[cur]];
}
}
ll res = INF;
for(int i = 0 ; i < S ; i++){
int v = X[i] , cur = v;
while(cur != -1){
res = min(res , h[v] + getF(is[id[cur]]) - h[cur] - h[cur]);
res = min(res , h[v] + getPt(id[r[cur]] , id[cur] , 1) - h[cur]);
cur = p[r[cur]];
}
}
ersSeg();
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
43352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
43608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
