| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1243142 | nai0610 | Factories (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n,q,dist[500009],mindist[500009];
int _t=0,tin[500009],tout[500009],par[20][500009];
vector<pair<int,i64>> adj[500009],bdj[500009];
void DFS(int u,int pu,i64 d)
{
tin[u]=++_t; dist[u]=d; par[0][u]=pu;
for(auto& v:adj[u])
if(v.first!=pu) DFS(v.first,u,d+v.second);
tout[u]=_t;
}
bool isA(int u,int v) {return tin[u]<=tin[v] and tout[v]<=tout[u];}
int LCA(int u,int v)
{
if(isA(u,v)) return u;
if(isA(v,u)) return v;
for(int i=19;i>=0;--i)
if(!isA(par[i][u],v)) u=par[i][u];
return par[0][u];
}
//i64 dist2(int u,int v) {return dist[u]+dist[v]-2*dist[LCA(u,v)];}
void xl()
{
int S,T; cin>>S>>T; i64 res=9e18;
vector<int> X(S),Y(T),Z(S+T);
for(int i=0;i<S;++i) {cin>>X[i]; Z[i]=++X[i];}
for(int i=0;i<T;++i) {cin>>Y[i]; Z[i+S]=++Y[i];}
sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];});
for(int i=1;i<S+T;++i) Z.push_back(LCA(Z[i],Z[i-1]));
sort(Z.begin(),Z.end(),[&](int x,int y){return tin[x]<tin[y];});
Z.resize(distance(Z.begin(),unique(Z.begin(),Z.end())));
stack<int> st; st.push(Z[0]); mindist[Z[0]]=3e18;
for(int i=1;i<Z.size();++i)
{
while(!isA(st.top(),Z[i])) st.pop();
bdj[st.top()].push_back({Z[i],dist[Z[i]]-dist[st.top()]});
bdj[Z[i]].push_back({st.top(),dist[Z[i]]-dist[st.top()]});
st.push(Z[i]); mindist[Z[i]]=3e18;
}
set<pair<i64,int>> dij;
for(int i=0;i<X.size();++i)
{
mindist[X[i]]=0;
dij.insert({0,X[i]});
}
while(!dij.empty())
{
int u=dij.begin()->second;
dij.erase(dij.begin());
for(auto& v:bdj[u])
{
if(mindist[v.first]>mindist[u]+v.second)
{
dij.erase({mindist[v.first],v.first});
mindist[v.first]=mindist[u]+v.second;
dij.insert({mindist[v.first],v.first});
}
}
}
for(int i=0;i<Y.size();++i) res=min(res,mindist[Y[i]]);
for(int i=0;i<Z.size();++i) bdj[Z[i]].clear();
cout<<res<<'\n';
}
int main()
{
if(fopen("D:/CPP/THEMIS/test.inp","r"))
{
freopen("D:/CPP/THEMIS/test.inp","r",stdin);
freopen("D:/CPP/THEMIS/test.out","w",stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>q;
for(int u,v,w,i=1;i<n;++i)
{
cin>>u>>v>>w; ++u; ++v;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
DFS(1,0,0); par[0][1]=1;
for(int i=1;i<20;++i) for(int j=1;j<=n;++j)
par[i][j]=par[i-1][par[i-1][j]];
while(q--) xl();
}
// No Raven here :((, cuz size limit exceeded