#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;
int sz;
int lc[22][n];
vector<ll> ds(n, 0), tin(n),tout(n);
int tim = 1;
int lca (int a, int b){
if(tin[a] <= tin[b] && tout[b] <= tout[a])return a;
if(tin[b] <= tin[a] && tout[a] <= tout[b])return b;
for(int i = 19 ; i >= 0; i--){
int na = lc[i][a];
if(tin[a] <= tin[b] && tout[b] <= tout[a])continue;
a = na;
}
return lc[0][a];
}
void dfs(int ps, int pr){
lc[0][ps] = pr;
for (int i = 1; i < 20; i++)
{
lc[i][ps] = lc[i-1][lc[i-1][ps]];
}
tin[ps] = tim++;
for(auto [to, d]:g[ps]){
if(to == pr)continue;
ds[to] = ds[ps] + d;
dfs(to, ps);
}
tout[ps] = tim++;
}
void Init(int N, int A[], int B[], int D[]) {
sz = N;
for(int i = 0; i < N-1; i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
}
long long Query(int S, int X[], int T, int Y[]) {
if(S*T >= 100000000){
q = priority_queue<array<ll,2>> ();
set<int> rem;
set<int> st;
for(int i = 0; i < T; i++){
st.insert(Y[i]);
}
for(int i = 0; i < S; i++){
q.push({0, X[i]});
dif[X[i]] = 0;
rem.insert(X[i]);
}
while(q.size()){
auto [dis, ps] = q.top();
q.pop();
//cout << dis << ' ' << ps << '\n';
dis = abs(dis);
if(dif[ps] < dis)continue;
if(st.count(ps)){
//for(int i = 0; i < sz; i++){
//cout << dif[i] << ' ' << i << '\n';
//}
//cout << '\n';
for(auto i:rem)dif[i] = inf;
return dis;
}
//cout << ps << '\n';
for(auto &[to, d]:g[ps]){
//cout << to << ' ' << d << '\n';
if(chmin(dif[to], dif[ps] + d)){
rem.insert(to);
q.push({-dif[to], to});
}
}
}
}else{
ll ans = inf;
for(int i = 0; i < S; i++){
for(int j = 0; j < T; j++){
int l = lca(X[i],Y[i]);
chmin(ans, ds[X[i]]+ds[Y[i]]-2*ds[l]);
}
}
return ans;
}
return inf;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
46160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
46172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
46160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
