| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 466993 | willi19 | 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>
using namespace std;
int n,q,dead[500100],sz[500100],centroid_tree[500100];
long long nearest[500100];
vector<int> g[500100],u,v;
vector<pair<int,long long> > l[500100];
vector<long long> dist[500100];
void get_sz(int start,int parent)
{
sz[start] =1;
for(int next:g[start])
{
if(dead[next]||next==parent)
continue;
get_sz(next,start);
sz[start] += sz[next];
}
}
int get_centroid(int start)
{
get_sz(start,-1);
int tree_sz = sz[start];
function<int (int,int) > dfs = [&] (int start, int parent)
{
for(int next:g[start])
{
if(dead[next]||next==parent)
continue;
if(sz[next]>tree_sz/2)
return dfs(next,start);
}
return start;
};
return dfs(start,-1);
}
int centroid_decomposition(int start)
{
int c = get_centroid(start);
dead[c] = true;
for(int next:g[c])
{
if(dead[next])
continue;
int nc = centroid_decomposition(next);
centroid_tree[nc] = c;
}
function<void (int,int,long long) > fill_dist = [&] (int start, int parent,long long d)
{
dist[start].push_back(d);
for(auto edge:l[start])
{
int next = edge.first;
if(dead[next]||next==parent)
continue;
fill_dist(next,start,d+edge.second);
}
};
fill_dist(c,-1,(long long) 0);
dead[c] = false;
return c;
}
void update(int ind)
{
int cur = ind;
int i=0;
while(cur != -1)
{
nearest[cur] = min(nearest[cur],dist[ind][i]);
cur = centroid_tree[cur];
i++;
}
}
void undo(int ind)
{
int cur = ind;
while(cur != -1)
{
nearest[cur] = 1000000000000000;
cur = centroid_tree[cur];
}
}
long long query(int ind)
{
long long ret = 10000000000000000;
int cur = ind;
int i=0;
while(cur != -1)
{
ret = min(ret,dist[ind][i]+nearest[cur]);
cur = centroid_tree[cur];
i++;
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>q;
for(int i=0;i<n-1;i++)
{
int a,b;
long long d;
cin>>a>>b>>d;
g[a].push_back(b);
g[b].push_back(a);
l[a].push_back({b,d});
l[b].push_back({a,d});
}
for(int i=0;i<n;i++)
centroid_tree[i] = -1;
centroid_decomposition(0);
for(int i=0;i<n;i++)
nearest[i] = 1000000000000000;
while(q--)
{
long long ans = 100000000000000000;
u.clear();
v.clear();
int s,t;
cin>>s>>t;
for(int i=0;i<s;i++)
{
int a;
cin>>a;
u.push_back(a);
}
for(int i=0;i<t;i++)
{
int a;
cin>>a;
v.push_back(a);
}
for(int ind:u)
update(ind);
for(int ind:v)
ans = min(ans,query(ind));
for(int ind:u)
undo(ind);
cout<<ans<<"\n";
}
}