| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 167542 | dessertion | 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"
#include <bits/stdc++.h>
using namespace std;
#define pb_ push_back
#define eb_ emplace_back
#define mp_ make_pair
//#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<long,long> pll;
typedef pair<int,int> pii;
const int MN = 5e5+10,LVL=21;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge{
int b,w;
};
vector<edge> adj[MN];
vector<int> adj2[MN];
int sz[MN],tree[MN],depth2[MN],parent[MN][LVL],touched[1000005],eid[MN],revid[MN],efirst[MN],id,cnt,last_touch;
int sparse[LVL][2*MN];
ll dist[MN],ans[MN];
bool done[MN];
int size(int u, int p){
sz[u] = 1;
for(auto e : adj[u]){
if(e.b==p||done[e.b])continue;
sz[u]+=size(e.b,u);
}
return sz[u];
}
int centroid(int u, int p, int tot){
for(auto e:adj[u])if(e.b!=p&&!done[e.b]&&2*sz[e.b]>=tot)return centroid(e.b,u,tot);
return u;
}
int decomp(int u, int last){
int cent = centroid(u,-1,size(u,-1));
tree[cent]=last;
done[cent]=1;
for(auto e : adj[cent]){
if(done[e.b])continue;
adj2[cent].pb_(decomp(e.b,cent));
}
return cent;
}
void Init(int n, int a[], int b[], int d[]){
for(int i = 0 ;i < n-1; i++){
adj[a[i]].pb_({b[i],d[i]});
adj[b[i]].pb_({a[i],d[i]});
}
memset(sparse,0x3f,sizeof(sparse));
decomp(0,-1);
function<void(int,int)> dfs = [&](int u, int p){
eid[u]=++id;
revid[id]=u;
efirst[id]=++cnt;
sparse[0][cnt]=id;
parent[u][0]=p;
for(auto e : adj[u]){
if(e.b==p)continue;
dist[e.b]=e.w+dist[u],depth2[e.b]=depth2[u]+1,dfs(e.b,u);
sparse[0][++cnt]=eid[u];
}
};
dfs(0,-1);
for(int i = 1; i < LVL ; i++){
for(int j = 0; j < n; j++){
parent[j][i] = parent[parent[j][i-1]][i-1];
}
}
/*
cout<<"SPARSE:\n";
for(int i = 1; i <= 2*n; i++){
cout<<sparse[0][i]<<" \n"[i==2*n];
}
*/
for(int i = 1; i <= 31-__builtin_clz(2*n); i++){
for(int j = 1; j +(1<<i)<=2*n; j++){
sparse[i][j] = min(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);
// cout<<sparse[i][j]<<" \n"[j+(1<<i)==2*n];
}
}
memset(ans,0x3f,sizeof(ans));
}
ll getDist(int u, int v){
/*function<int(int,int)> lca = [&](int a, int b){
if(depth2[a]>depth2[b])swap(a,b);
int diff = depth2[b]-depth2[a];
for(int i =0 ; i < LVL; i++)if((diff>>i)&1)b=parent[b][i];
if(b==a)return a;
for(int i = LVL-1; i>=0; i--){
if(parent[a][i]!=parent[b][i])a=parent[a][i],b=parent[b][i];
}
return parent[a][0];
};*/
function<int(int,int)> lca = [&](int a, int b){
a=efirst[eid[a]],b=efirst[eid[b]];
if(a>b)swap(a,b);
int diff = b-a;
int lg = 31-__builtin_clz(diff);
int ret = min(sparse[lg][a],sparse[lg][b-(1<<lg)+1]);
return revid[ret];
};
int anc = lca(u,v);
return abs(dist[u]-dist[anc])+abs(dist[v]-dist[anc]);
}
long long Query(int s, int x[], int t, int y[]){
for(int i = 0 ; i < s ; i++){
for(int v = x[i]; v!=-1; v=tree[v]){
ans[v] = min(ans[v],getDist(x[i],v));
touched[last_touch++]=v;
}
}
ll ret = INF;
for(int i = 0; i < t; i ++){
for(int v = y[i]; v!=-1; v=tree[v]){
ret=min(ret,getDist(v,y[i])+ans[v]);
}
}
for(int i = last_touch-1;i>=0; i--)ans[touched[i]]=INF;
last_touch=0;
return ret;
}
int main()
{
// freopen("../input.txt","r",stdin);
// freopen("../output.txt","w",stdout);
int N, Q;
assert(scanf("%i %i", &N, &Q) == 2);
int *A = (int *)malloc(sizeof(int) * (N - 1));
int *B = (int *)malloc(sizeof(int) * (N - 1));
int *D = (int *)malloc(sizeof(int) * (N - 1));
for (int a = 0; a < N - 1; a++)
{
assert(scanf("%i %i %i", A + a, B + a, D + a) == 3);
}
Init(N, A, B, D);
for (int a = 0; a < Q; a++)
{
int S, T;
assert(scanf("%i %i", &S, &T) == 2);
int *X = (int *)malloc(sizeof(int) * S);
int *Y = (int *)malloc(sizeof(int) * T);
for (int b = 0; b < S; b++)
{
assert(scanf("%i", X + b) == 1);
}
for (int b = 0; b < T; b++)
{
assert(scanf("%i", Y + b) == 1);
}
printf("%lld\n", Query(S, X, T, Y));
free(X);
free(Y);
}
free(A);
free(B);
free(D);
}