제출 #1153521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153521		sasde	공장들 (JOI14_factories)	C++20	0 / 100	29 ms	24384 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){
    if(g[u]==1){
        ans=min(ans,dp[u]);
    }
    for(ii v:a1[u]){
        if(v.fi==cha)continue;
        if(l[u]==v.fi){
            if(dp[v.fi]>=dp2[u]+v.se){
            l[u]=v.fi;
            dp2[v.fi]=dp[v.fi];
            dp[v.fi]=dp2[u]+v.se;
            }
        }
        else{
            if(dp[v.fi]>=dp[u]+v.se){
            l[u]=v.fi;
            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;
    }
    for(ii v:a1[u]){
        if(v.fi==cha)continue;
        dfs2(v.fi,u);
        if(dp[u]>=dp[v.fi]+v.se){
            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;


}
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()){
                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);
        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();
        }
        res.clear();

        return ans;
}

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