#include "factories.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <map>
using namespace std;
vector < pair < long long , long long > > Next[500005];
pair < long long , long long > Father[35][500005];
//min
long long vis[500005]={0};
long long use[500005]={0};
long long sz[500005]={0};
long long big[500005]={0};
long long tt[500005]={0};
long long root,now=1,now2=0;
pair < long long , long long > a[500005],b[500005];
vector < long long > have;
vector < int > how;
void F2(long long here)
{
how.push_back(here);
sz[here]=1;
big[here]=0;
vis[here]=now;
for(auto i:Next[here])
{
if(!use[i.first]&&vis[i.first]!=now)
{
F2(i.first);
sz[here]+=sz[i.first];
big[here]=max(big[here],sz[i.first]);
}
}
}
void F3(long long here,long long root,long long fa,long long con,long long deg)
{
Father[deg][here]=make_pair(root,con);
for(auto i:Next[here])
{
if(i.first!=fa&&!use[i.first]) F3(i.first,root,here,con+i.second,deg);
}
}
void F(long long here,long long deg)
{
long long t=2e9;
now++;
how.clear();
F2(here);
for(auto i:how)
{
if(max(sz[here]-sz[i],big[i])<=t)
{
t=max(sz[here]-sz[i],big[i]);
root=i;
}
}
F3(root,root,-1,0,deg);
use[root]=1;
for(auto i:Next[root]) if(!use[i.first]) F(i.first,deg+1);
}
void Init(int N, int A[], int B[], int D[])
{
int i,j;
for(i=0;i<20;i++) for(j=0;j<N;j++) Father[i][j]=make_pair(-1,-1);
for(i=0;i<N-1;i++)
{
Next[A[i]].push_back(make_pair((long long) B[i],(long long) D[i]));
Next[B[i]].push_back(make_pair((long long) A[i],(long long) D[i]));
}
F(0,0);
}
long long Query(int S, int X[], int T, int Y[])
{
long long ans=1e18,i,j;
now2++;
have.clear();
for(i=0;i<S;i++)
{
for(j=0;j<20;j++)
{
if(Father[j][X[i]].first==-1) break;
if(a[Father[j][X[i]].first].first!=now2) a[Father[j][X[i]].first]=make_pair(now2,Father[j][X[i]].second);
else a[Father[j][X[i]].first].second=min(a[Father[j][X[i]].first].second,Father[j][X[i]].second);
if(Father[j][X[i]].first!=now2)
{
have.push_back(Father[j][X[i]].first);
Father[j][X[i]].first=now2;
}
}
}
for(i=0;i<T;i++)
{
for(j=0;j<20;j++)
{
if(Father[j][Y[i]].first==-1) break;
if(b[Father[j][Y[i]].first].first!=now2) b[Father[j][Y[i]].first]=make_pair(now2,Father[j][Y[i]].second);
else b[Father[j][Y[i]].first].second=min(b[Father[j][Y[i]].first].second,Father[j][Y[i]].second);
if(Father[j][Y[i]].first!=now2)
{
have.push_back(Father[j][Y[i]].first);
Father[j][Y[i]].first=now2;
}
}
}
for(auto i:have)
{
if(a[i].first!=now2||b[i].first!=now2) continue;
ans=min(ans,a[i].second+b[i].second);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
13036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
13036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
