#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 5e5 + 5,m,timer = 0;
vector<set<pair<int,int>>>adj(n);
vi sub(n),par(n,-1),in(n),out(n);
vl d(n),res(n,inf);
vi when(n);
vvi dp(n,vi(21,1));
void orig_dfs(int i,int p,ll w)
{
if (p != -1)d[i] = d[p] + w;
if (p != -1)dp[i][0] = p;
for (int power = 1;power<=20;power++)dp[i][power] = dp[dp[i][power - 1]][power - 1];
in[i] = ++timer;
for (auto val:adj[i]){
int c = val.first;
ll wt = val.second;
if (c != p)orig_dfs(c,i,wt);
}
out[i] = ++timer;
}
bool is_anc(int i,int j)
{
return in[i] <= in[j] && out[i] >= out[j];
}
int lca(int i,int j)
{
if (in[i] > in[j])swap(i,j);
int ret = j;
for (int power = 20;power >= 0;power--){
if (!is_anc(dp[ret][power],i))ret = dp[ret][power];
}
if (i == j)return i;
return dp[ret][0];
}
ll dist(int i,int j)
{
if (in[i] > in[j])swap(i,j);
int l = lca(i,j);
return d[i] + d[j] - 2 * d[l];
}
int dfs(int i,int p)
{
for (auto val:adj[i]){
int c = val.first;
if (c != p)sub[i] += dfs(c,i);
}
return sub[i];
}
int centroid(int i,int p,int sz)
{
for (auto val:adj[i]){
int c = val.first;
if (c != p && sub[c] > sz/2)return centroid(c,i,sz);
}
return i;
}
void decompose(int i,int p,ll w)
{
int cent = centroid(i,p,dfs(i,-1));
par[cent] = p;
for (auto val:adj[cent]){
int nxt = val.first;
ll wt = val.second;
adj[nxt].erase({cent,wt});
decompose(nxt,cent,wt);
}
}
void update(int i)
{
int cur = i;
while (cur != -1){
res[cur] = min(res[cur],dist(cur,i));
cur = par[cur];
}
}
ll query(int i)
{
ll ret = inf;
int cur = i;
while (cur != -1){
ret = min(ret,dist(cur,i) + res[cur]);
cur = par[cur];
}
return ret;
}
void reset(int i)
{
while (i != -1){
res[i] = inf;
i = par[i];
}
}
void Init(int N, int a[], int b[], int d[]) {
n = N;
for (int i = 0;i<n - 1;i++){
int u = a[i],v = b[i],w = d[i];
u++,v++;
adj[u].insert({v,w}),adj[v].insert({u,w});
}
orig_dfs(1,-1,0);
decompose(1,-1,0);
update(1);
}
long long Query(int a, int v1[], int b, int v2[]) {
ll ans = inf;
for (int i = 0;i<a;i++)update(v1[i] + 1);
for (int i = 0;i<b;i++)ans = min(ans,query(v2[i] + 1));
for (int i = 0;i<a;i++)reset(v1[i] + 1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
100436 KB |
Output is correct |
| 2 |
Correct |
5541 ms |
108652 KB |
Output is correct |
| 3 |
Execution timed out |
8093 ms |
108608 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
91 ms |
100196 KB |
Output is correct |
| 2 |
Execution timed out |
8074 ms |
177156 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
100436 KB |
Output is correct |
| 2 |
Correct |
5541 ms |
108652 KB |
Output is correct |
| 3 |
Execution timed out |
8093 ms |
108608 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
