| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 111638 | discoverMeMe | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=500001;
int n,cnt,st[N],ed[N],par[N][20],lvl[N],a,b,c,cand[N*2],ext[N],pcnt;
long long U[N],V[N],xx,len[N],MAX=LLONG_MAX>>2;
bool blc[N];
vector<pair<int,int>> gr[N];
int lca(int x,int y)
{
if (lvl[x]>lvl[y])
swap(x,y);
int up=lvl[y]-lvl[x];
ford(i,19,0)
if(up&(1<<i))
y=par[y][i];
if (x==y)
return x;
for (int i=19;i>=0;i--)
if (par[x][i]!=par[y][i])
{
x=par[x][i];
y=par[y][i];
}
return par[x][0];
}
void dfs(int x)
{
blc[x] = 1;
for (int i=0;i<gr[x].size();i++){
pair<int, int> p = gr[x][i];
if (blc[p.first]) continue;
st[p.first] = ++cnt;
lvl[cnt] = lvl[st[x]] + 1;
len[cnt] = len[st[x]] + p.second;
par[cnt][0] = st[x];
for (int i=1;i<20;i++) par[cnt][i] = par[par[cnt][i-1]][i-1];
dfs(p.first);
}
ed[st[x]] = cnt;
}
void Init(int N,int A[],int B[],int D[])
{
fori(0,N-1)
{
gr[A[i]].push_back({B[i],D[i]});
gr[B[i]].push_back({A[i],D[i]});
}
st[0]=cnt=1;
dfs(0);
}
int pdfs(int x)
{
U[x]=V[x]=MAX;
if(ext[cand[x]]==1)
U[x]=0;
if(ext[cand[x]]==2)
V[x]=0;
int e=x+1;
while(e<pcnt&&cand[e]<=ed[cand[x]])
{
a=pdfs(e);
U[x]=min(U[x],U[e]+len[cand[e]]-len[cand[x]]);
V[x]=min(V[x],V[e]+len[cand[e]]-len[cand[x]]);
e=a;
}
xx=min(xx,U[x]+V[x]);
ext[cand[x]]=0;
return e;
}
long long Query(int S,int X[],int T,int Y[])
{
pcnt=0;
for(int i=0;i<S;i++)
{
cand[pcnt++]=st[X[i]];
ext[st[X[i]]]=1;
}
for(int i=0;i<T;i++)
{
cand[pcnt++]=st[Y[i]];
ext[st[Y[i]]]=2;
}
sort(cand,cand+pcnt);
for(int i=1;i<S+T;i++)
cand[pcnt++]=lca(cand[i-1],cand[i]);
sort(cand,cand+pcnt);
pcnt=unique(cand,cand+pcnt)-cand;
xx=MAX;
pdfs(0);
return xx;
}
//*
int aa[N],bb[N],cc[N],dd[N],ee[N];
int main()
{
cin.sync_with_stdio(0);
cin.tie(0);
freopen("01-01.txt", "r", stdin);
int q;
cin>>n>>q;
fori(0,n-1)
{
cin>>aa[i]>>bb[i]>>cc[i];
}
Init(n,aa,bb,cc);
forj(0,q)
{
cin>>a>>b;
fori(0,a)
cin>>dd[i];
fori(0,b)
cin>>ee[i];
cout<<Query(a,dd,b,ee)<<"\n";
}
//cout<<cnt<<endl;
return 0;
}/**/