제출 #1153518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153518		sasde	공장들 (JOI14_factories)	C++20	0 / 100	14 ms	26176 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]);
        // cout << 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;
        }
        // else if(dp[u]==dp[v.fi]+v.se)dp2[u]
        // dp[u]=min(dp[v.fi]+v.se,dp[u]);
    }
}
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;
}
int x[N],y[N],ss,tt;
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];
}
// int g[N];
// void solve(){
//     cin >> n >> q;
//     for(int i=1;i<n;++i){
//         int u,v,w;
//         cin >> u >> v >> w;
//         ++u,++v;
//         a[u].emb(v,w);
//         a[v].emb(u,w);
//     }
//     for(int i=1;i<=n;++i)dp[i]=dp2[i]=1e18,g[i]=-1;
//     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];
//     }
//     // memset(g,-1,sizeof g);

// }
void Init(int q,int w[],int e[],int r[]){
    for(int i=0;i<q-1;++i){
        int u=w[i];
        int v=e[i];
        ++u,++v;
        a[u].emb(v,r[i]);
        a[v].emb(u,r[i]);
    }
    dfs(1,-1);
     for(int j=1;j<=lg;++j)
    for(int i=1;i<=q;++i){
        up[i][j]=up[up[i][j-1]][j-1];
    }
    for(int i=1;i<=q;++i)dp[i]=1e18;
    memset(g,-1,sizeof g);


}
long long Query(int S,int u[],int T,int v[]){
    // while(q--){
        ans=1e18;
        // cin >> ss >> tt;
        for(int i=0;i<ss;++i){
            // cin >> x[i];
            x[i]++;
            res.emb(x[i]);
            g[x[i]]=1;
            // cout <<x[i]<<" ";
        }

        for(int i=0;i<tt;++i){
            // cin >> y[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]));
            // cout <<res[i]<<" "<<res[i+1]<<" "<<lca(res[i],res[i+1])<<'\n';
        }

        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();
            // cout <<i<<" ";
        }
        res.clear();

        return ans;
    // }
}
// main()
// {
//   srand(time(0));
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     if(fopen(task".inp","r")){
//       freopen(task".inp","r",stdin);
//       freopen(task".out","w",stdout);
//     }
//     int t=1;
//  //   cin >> t;
// while(t--){
//     solve();
//     cout<<'\n';
// }

// }

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