| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 76224 | nxteru | 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 <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstring>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
#define B 1500
struct query{
int s,t;
vector<int>x,y;
};
int n,q,k,par[500005][20],dp[500005],pr[500005],id[500005];
ll x[500005],y[500005],ans;
vector<P>g[500005];
vector<P>G[500005];
vector<query>Q;
vector<P>cm;
void dfs(int v,int p,int d){
pr[v]=k++;
par[v][0]=p;
dp[v]=d;
for(int i=0;i<g[v].size();i++)if(g[v][i].F!=p)dfs(g[v][i].F,v,d+1);
}
int lca(int v,int u){
if(dp[v]>dp[u])swap(v,u);
for(int i=0;i<20;i++){
if((dp[u]-dp[v])>>i&1)u=par[u][i];
}
if(u==v)return v;
for(int i=19;i>=0;i--){
if(par[v][i]!=par[u][i]){
v=par[v][i];
u=par[u][i];
}
}
return par[v][0];
}
void s_dfs(int v,int p,int r,ll d){
if(id[v]!=-1){
if(r!=-1){
G[r].PB(P(id[v],d));
G[id[v]].PB(P(r,d));
}
r=id[v];
d=0;
}
for(int i=0;i<g[v].size();i++){
if(g[v][i].F!=p)s_dfs(g[v][i].F,v,r,d+g[v][i].S);
}
}
void a_dfs(int v,int p){
for(int i=0;i<G[v].size();i++){
int u=G[v][i].F;
ll c=G[v][i].S;
if(u!=p){
a_dfs(u,v);
x[v]=min(x[v],x[u]+c);
y[v]=min(y[v],y[u]+c);
}
}
ans=min(ans,x[v]+y[v]);
}
int main(void){
scanf("%d%d",&n,&q);
for(int i=0;i<n-1;i++){
int a,b;
ll c;
scanf("%d%d%lld",&a,&b,&c);
g[a].PB(P(b,c));
g[b].PB(P(a,c));
}
dfs(0,-1,0);
for(int i=0;i<19;i++){
for(int v=0;v<n;v++){
if(par[v][i]==-1)par[v][i+1]=-1;
else par[v][i+1]=par[par[v][i]][i];
}
}
while(q){
for(int i=0;i<n;i++){
id[i]=-1;
G[i].clear();
}
k=0;
cm.clear();
while(k<B&&q){
query o;
scanf("%d%d",&o.s,&o.t);
for(int i=0;i<o.s;i++){
int a;
scanf("%d",&a);
if(id[a]==-1){
id[a]=k++;
cm.PB(P(pr[a],a));
}
o.x.PB(a);
}
for(int i=0;i<o.t;i++){
int a;
scanf("%d",&a);
if(id[a]==-1){
id[a]=k++;
cm.PB(P(pr[a],a));
}
o.y.PB(a);
}
Q.PB(o);
q--;
}
sort(cm.begin(),cm.end());
for(int i=1;i<cm.size();i++){
int a=lca(cm[i].F,cm[i-1].F);
if(id[a]==-1){
id[a]=k++;
}
}
s_dfs(0,-1,-1,0);
for(int i=0;i<Q.size();i++){
ans=INF;
for(int j=0;j<k;j++){
x[j]=INF;
y[j]=INF;
}
for(int j=0;j<Q[i].x.size();j++)x[id[Q[i].x[j]]]=0;
for(int j=0;j<Q[i].y.size();j++)y[id[Q[i].y[j]]]=0;
a_dfs(0,-1);
printf("%lld\n",ans);
}
}
}