Submission #786748

#	Time	Username	Problem	Language	Result	Execution time	Memory
786748		winter0101	Factories (JOI14_factories)	C++14	100 / 100	5306 ms	192712 KiB

factories

#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
vector<edg>lon[500009];
long long dis[500009];
int dep[500009];
int st[500009][21];
int sub[500009];
int use[500009];
int in[500009];
int ck[500009];
int cnt=0;
bool cmp(int i,int j){
return in[i]<in[j];
}
void dfs(int u,int par){
    in[u]=++cnt;
    for (auto v:g[u]){
        if (v.v==par)continue;
        dis[v.v]=v.w+dis[u];
        dep[v.v]=dep[u]+1;
        st[v.v][0]=u;
        dfs(v.v,u);
    }
}
inline int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for (int i=18;i>=0;i--){
    if (k>>i&1){
        u=st[u][i];
    }
}
if (u==v)return u;
for (int i=18;i>=0;i--){
    if (st[u][i]==0||st[v][i]==0)continue;
    if (st[u][i]!=st[v][i]){
        u=st[u][i];
        v=st[v][i];
    }
}
return st[u][0];
}
inline long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
long long cac[500009];//min 1
long long buoi[500009];//min 2
void Init(int n,int a[],int b[],int d[]){
for (int i=0;i<n-1;i++){
    a[i]++;
    b[i]++;
    g[a[i]].push_back({b[i],d[i]});
    g[b[i]].push_back({a[i],d[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
    for (int j=1;j<=n;j++){
        cac[j]=buoi[j]=1e17;
        st[j][i]=st[st[j][i-1]][i-1];
    }
}
}
long long ans=1e17;
void redfs(int u){
    if (use[u]==1)cac[u]=0;
    if (use[u]==2)buoi[u]=0;
    for (auto v:lon[u]){
        redfs(v.v);
        cac[u]=min(cac[u],cac[v.v]+v.w);
        buoi[u]=min(buoi[u],buoi[v.v]+v.w);
    }
    ans=min(ans,cac[u]+buoi[u]);
}
long long Query(int s,int x[],int t,int y[]){
vector<int>tp;
for (int i=0;i<s;i++){
    use[x[i]+1]=1;
    ck[x[i]+1]=1;
    tp.push_back(x[i]+1);
}
for (int i=0;i<t;i++){
    use[y[i]+1]=2;
    ck[y[i]+1]=1;
    tp.push_back(y[i]+1);
}
sort(tp.begin(),tp.end(),cmp);
for (int i=1;i<(int)tp.size();i++){
    int u=tp[i],v=tp[i-1];
    if (ck[lca(u,v)]==0){
        ck[lca(u,v)]=1;
        tp.push_back(lca(u,v));
    }
}
sort(tp.begin(),tp.end(),cmp);
vector<int>dit;
for (auto v:tp){
    if (dit.empty()){
        dit.push_back(v);
    }
    else {
        while (!dit.empty()&&lca(dit.back(),v)!=dit.back())dit.pop_back();
        lon[dit.back()].push_back({v,cal(dit.back(),v)});
        dit.push_back(v);
    }
}
ans=1e17;
redfs(dit[0]);
for (auto v:tp){
    ck[v]=0;
    lon[v].clear();
    cac[v]=buoi[v]=1e17;
}
for (int i=0;i<s;i++){
    use[x[i]+1]=0;
}
for (int i=0;i<t;i++){
    use[y[i]+1]=0;
}
return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67