| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 222895 | mhy908 | 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.
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
inline int readChar();
template<class T=int> inline T readInt();
template<class T> inline void writeInt(T x, char end=0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size=4096;
inline int getChar(){
static char buf[buf_size];
static int len=0, pos=0;
if(pos==len)pos=0, len=fread(buf, 1, buf_size, stdin);
if(pos==len)return -1;
return buf[pos++];
}
inline int readChar(){
int c=getChar();
while(c<=32)c=getChar();
return c;
}
template <class T>
inline T readInt(){
int s=1, c=readChar();
T x=0;
if(c=='-')s=-1, c=getChar();
while('0'<= c&&c<='9')x=x*10+c-'0', c=getChar();
return s==1?x:-x;
}
int n, q, siz[500010], d[500010], sparse[500010][30], centpar[500010];
vector<pil> link[500010];
bool ch[500010];
LL dep[500010];
void dfs(int num, int par){
siz[num]=1;
d[num]=d[par]+1;
sparse[num][0]=par;
for(auto i:link[num]){
if(i.F==par)continue;
dep[i.F]=dep[num]+i.S;
dfs(i.F, num);
siz[num]+=siz[i.F];
}
}
int lca(int x, int y){
if(d[x]>d[y])swap(x, y);
for(int i=20; i>=0; i--){
if(d[y]-d[x]>=(1<<i))y=sparse[y][i];
}
if(x==y)return x;
for(int i=20; i>=0; i--){
if(sparse[x][i]!=sparse[y][i]){
x=sparse[x][i];
y=sparse[y][i];
}
}
return sparse[x][0];
}
inline LL dist(int x, int y){return dep[x]+dep[y]-2*dep[lca(x, y)];}
int get_centroid(int num, int par, int sz){
bool flag=true;
for(auto i:link[num]){
if(ch[i.F])continue;
if(siz[i.F]>sz/2)flag=false;
}
if(flag)return num;
for(auto i:link[num]){
if(i.F==par||ch[i.F])continue;
int temp=siz[i.F];
siz[num]=sz-siz[i.F];
siz[i.F]=sz;
int ret=get_centroid(i.F, num, sz);
if(ret)return ret;
siz[num]=sz;
siz[i.F]=temp;
}
return 0;
}
void make_centroidtree(int num, int par){
int cen=get_centroid(num, 0, siz[num]);
ch[cen]=true;
centpar[cen]=par;
for(auto i:link[cen]){
if(ch[i.F])continue;
make_centroidtree(i.F, cen);
}
}
LL arr[500010];
vector<int> up[500010];
vector<LL> pardis[500010];
inline void update(int num){
for(int i=0; i<up[num].size(); i++)arr[up[num][i]]=min(arr[up[num][i]], pardis[num][i]);
}
inline LL query(int num){
LL ret=llinf;
for(int i=0; i<up[num].size(); i++)ret=min(ret, arr[up[num][i]]+pardis[num][i]);
return ret;
}
void cl(int num){
for(int i=0; i<up[num].size(); i++){
if(arr[up[num][i]]==llinf)break;
arr[up[num][i]]=llinf;
}
}
int arr1[1000010];
int main(){
scanf("%d %d", &n, &q);
for(int i=1; i<n; i++){
int a=readInt();
int b=readInt();
LL c=(LL)readInt();
link[a+1].pb(mp(b+1, c));
link[b+1].pb(mp(a+1, c));
}
for(int i=1; i<=n; i++)arr[i]=llinf;
dfs(1, 0);
for(int j=1; j<=20; j++){
for(int i=1; i<=n; i++){
sparse[i][j]=sparse[sparse[i][j-1]][j-1];
}
}
make_centroidtree(1, 0);
for(int i=1; i<=n; i++){
int now=i;
while(now){
up[i].pb(now);
pardis[i].pb(dist(i, now));
now=centpar[now];
}
}
while(q--){
int n1=readInt();
int n2=readInt();
LL ans=llinf;
for(int i=1; i<=n1; i++){
arr1[i]=readInt();
update(arr1[i]+1);
}
for(int i=1; i<=n2; i++){
int a=readInt();
ans=min(ans, query(a+1));
}
for(int i=1; i<=n1; i++)cl(arr1[i]+1);
printf("%lld\n", ans);
}
}