#include "factories.h"
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int,int> > v[500005];
long long cum[500005],di[30][500005];
bool del[500005];
int dep[500005],dp[20][500005],par[500005],sz[500005];
void dfs(int node,int p)
{
for (auto u:v[node])
{
if (u.first!=p)
{
dep[u.first]=dep[node]+1;
cum[u.first]=cum[node]+u.second;
dp[0][u.first]=node;
dfs(u.first,node);
}
}
}
int lca(int u,int v)
{
if (dep[u]<dep[v])
swap(u,v);
int d=dep[u]-dep[v];
for (int i=0;i<20;i++)
{
if (d&(1<<i))
u=dp[i][u];
}
if (u==v)
return u;
for (int i=19;i>=0;i--)
{
if (dp[i][u]!=dp[i][v])
{
u=dp[i][u];
v=dp[i][v];
}
}
return dp[0][u];
}
long long dist(int a,int b)
{
return cum[a]+cum[b]-2*cum[lca(a,b)];
}
void pre(int node,int p)
{
sz[node]=1;
for (auto u:v[node])
{
if (!del[u.first] && u.first!=p)
{
dfs(u.first,node);
sz[node]+=sz[u.first];
}
}
}
int find(int node,int p,int n)
{
for (auto u:v[node])
{
if (u.first!=p && !del[u.first] && sz[u.first]>n/2)
return find(u.first,node,n);
}
return node;
}
void dfs2(int node,int p)
{
pre(node,-1);
int c=find(node,-1,sz[node]);
par[c]=p;
del[c]=1;
for (auto u:v[c])
{
if (!del[u.first])
dfs2(u.first,c);
}
}
long long ans[500005];
void update(int node,bool mem)
{
int cur=node,cnt=0;
while (cur!=-1)
{
if (di[cnt][node]==-1)
di[cnt][node]=dist(cur,node);
if (mem)
ans[cur]=(1LL<<60);
else
ans[cur]=min(ans[cur],di[cnt][node]);
cur=par[cur];
cnt++;
}
}
long long query(int node)
{
int cur=node,cnt=0;
long long ret=(1LL<<60);
while (cur!=-1)
{
ret=min(ret,di[cnt][node]+ans[cur]);
cur=par[cur];
cnt++;
}
return ret;
}
void Init(int n,int a[],int b[],int d[])
{
for (int i=0;i<n-1;i++)
{
v[a[i]].push_back({b[i],d[i]});
v[b[i]].push_back({a[i],d[i]});
}
memset(dp,-1,sizeof(dp));
dfs(0,-1);
for (int i=1;i<20;i++)
{
for (int x=0;x<n;x++)
{
if (dp[i-1][x]!=-1)
dp[i][x]=dp[i-1][dp[i-1][x]];
}
}
memset(di,-1,sizeof(di));
dfs2(0,-1);
for (int i=0;i<n;i++)
update(i,1);
}
long long Query(int s,int x[],int t,int y[])
{
/*long long ret=(1LL<<60);
for (int i=0;i<s;i++)
{
for (int j=0;j<t;j++)
ret=min(ret,dist(x[i],y[j]));
}
return ret;*/
for (int i=0;i<s;i++)
update(x[i],0);
long long ret=(1LL<<60);
for (int i=0;i<t;i++)
ret=min(ret,query(y[i]));
for (int i=0;i<s;i++)
update(x[i],1);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
169024 KB |
Output is correct |
| 2 |
Correct |
852 ms |
177276 KB |
Output is correct |
| 3 |
Runtime error |
733 ms |
353960 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
353960 KB |
Output is correct |
| 2 |
Runtime error |
4989 ms |
425072 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
169024 KB |
Output is correct |
| 2 |
Correct |
852 ms |
177276 KB |
Output is correct |
| 3 |
Runtime error |
733 ms |
353960 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
