Submission #1153549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153549		sasde	Factories (JOI14_factories)	C++20	100 / 100	4278 ms	179964 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define ii pair<int,long long>
#define se second
#define fi first
#define emb emplace_back
using namespace std;
const int N=5e5+5,lg=19;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
vector<ii>a[N],a1[N];
int tin[N],t,tout[N],g[N],h[N],up[N][lg+5],l[N];
long long f[N],ans,dp[N],dp2[N];
void dfs3(int u,int cha){
        // cout <<u<<" "<<dp[u]<<'\n';;
            // cout <<dp[v.fi]<<" "<<v.fi<<'\n';

    if(g[u]==1){
        ans=min(ans,dp[u]);
    }
    for(ii v:a1[u]){
        if(v.fi==cha)continue;
 // cout<<v.fi<<" "<<dp[v.fi]<<" "<<u<<" "<<v.se<<" "<<dp[u]<<" "<<l[u]<<'\n';
        if(l[u]==v.fi){
            if(dp[v.fi]>=dp2[u]+v.se){
            l[v.fi]=u;
            dp2[v.fi]=dp[v.fi];
            dp[v.fi]=dp2[u]+v.se;
            }
        }
        else{


            if(dp[v.fi]>=dp[u]+v.se){
            l[v.fi]=u;
            dp2[v.fi]=dp[v.fi];
            dp[v.fi]=dp[u]+v.se;
            }
        }
        dfs3(v.fi,u);
    }
}
void dfs2(int u,int cha){
    if(g[u]==0){
        dp[u]=0;dp2[u]=0;
    }
    for(ii v:a1[u]){
        if(v.fi==cha)continue;
        dfs2(v.fi,u);
        if(dp[u]>=dp[v.fi]+v.se){
            // cout <<u<<" "<<v.fi<<'\n';
            l[u]=v.fi;
            dp2[u]=dp[u];
            dp[u]=dp[v.fi]+v.se;
        }
    }
}
void dfs(int u,int cha){
    tin[u]=++t;
    for(ii v:a[u]){
        if(v.fi==cha)continue;
        h[v.fi]=h[u]+1;
        up[v.fi][0]=u;
        f[v.fi]=f[u]+v.se;
        dfs(v.fi,u);
    }
    tout[u]=t;
}
stack<int>s;
int lca(int u,int v){
    if(h[u]<h[v])swap(u,v);
    for(int j=lg;j>=0;--j)if(h[u]-h[v]>=(1<<j))u=up[u][j];
    if(u==v)return u;
for(int j=lg;j>=0;--j){
    if(up[u][j]!=up[v][j]){
        u=up[u][j];
        v=up[v][j];
    }
}

    return up[u][0];
}
long long  kc(int u,int v){
    return f[u]+f[v]-f[lca(u,v)]*2;
}
vector<int>res,res1;
bool cmp(int x,int y){
    return tin[x]<tin[y];
}
bool cha(int x,int y){
    return tout[x]>=tout[y]&&tin[x]<=tin[y];
}
void Init(int n,int A[],int B[],int D[]){
    for(int i=0;i<n-1;++i){
        int u=A[i];
        int v=B[i];
        ++u,++v;
        a[u].emb(v,D[i]);
        a[v].emb(u,D[i]);
    }
    dfs(1,-1);
     for(int j=1;j<=lg;++j)
    for(int i=1;i<=n;++i){
        up[i][j]=up[up[i][j-1]][j-1];
    }
    for(int i=1;i<=n;++i)dp[i]=dp2[i]=1e18,g[i]=-1,l[i]=0;
}
long long Query(int S,int x[],int T,int y[]){
        ans=1e18;
        for(int i=0;i<S;++i){
            x[i]++;
            res.emb(x[i]);
            g[x[i]]=1;
        }

        for(int i=0;i<T;++i){
            y[i]++;
            res.emb(y[i]);
            g[y[i]]=0;
        }
        
        sort(res.begin(),res.end(),cmp);
        int sz=res.size();

        for(int i=0;i<sz-1;++i){
            res.emb(lca(res[i],res[i+1]));
        }

        sort(res.begin(),res.end());
        res.erase(unique(res.begin(),res.end()),res.end());
        sort(res.begin(),res.end(),cmp);

        for(int i:res){
            while(!s.empty()&&!cha(s.top(),i))s.pop();
            if(!s.empty()){
                // if(i==4&&s.top()==1)cout<<kc(i,s.top())<<'\n';
                a1[s.top()].emb(i,kc(i,s.top()));
                a1[i].emb(s.top(),kc(i,s.top()));
            }
            s.push(i);
        }

        dfs2(res[0],-1);
        // for(int i=1;i<=10;++i)cout <<l[i]<<" ";
        dfs3(res[0],-1);

        while(!s.empty())s.pop();
        for(int i:res){
            g[i]=-1;dp[i]=dp2[i]=1e18;
            if(a1[i].size())
            a1[i].clear();
        l[i]=0;
        }
        res.clear();

            return ans;
    }
    // int q,n,A[N],B[N],D[N],x[N],y[N],T,S;
    // main(){
    //     ios_base::sync_with_stdio(false);
    //     cin.tie(NULL);
    //     cout.tie(NULL);
    //             freopen("a.inp","r",stdin);
    //     freopen("a.out","w",stdout);
    //     cin >> n >> q;
    //     for(int i=0;i<n-1;++i){
    //         cin >> A[i] >> B[i] >> D[i];
    //     }
    //     Init(n,A,B,D);
    //     while(q--){
    //         cin >> S >> T;
    //         for(int i=0;i<S;++i){
    //         cin >> x[i];
    //         }
    //         for(int i=0;i<T;++i)cin >> y[i];
    //             cout << Query(S,x,T,y)<<'\n';
    //         // for(int i=1;i<=n;++i)cout <<g[i]<<'\n';
    //         // cout <<res.size()<<'\n';
    //     }
    // }

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