Submission #1154773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154773		son2008	Factories (JOI14_factories)	C++20	100 / 100	1862 ms	162988 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,ll>
#define fi first
#define se second
//#define int long long
#define ll long long
#define mp make_pair
#define lg2 20
#define iii pair<int,ii>
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e5+5;
const int mod=1e9+7;
int n,cc[maxn],q,k;
vector<ii>a[maxn],e[maxn];
int h[maxn],P[maxn][lg2+1],tin[maxn],tout[maxn],timer,type[maxn];
int d[maxn];
ll dp[maxn][2],ans,dist[maxn];
void pre(int u,int cha)
{
    tin[u]=++timer;
    for(ii v:a[u])
    {
        if(v.fi==cha)continue;
        h[v.fi]=h[u]+1;
        P[v.fi][0]=u;
        dist[v.fi]=dist[u]+v.se;
        pre(v.fi,u);
    }
    tout[u]=timer;
}
void build_lca(){
    for(int j=1;j<=lg2;j++){
        for(int i=1;i<=n;i++)
            P[i][j]=P[P[i][j-1]][j-1];
    }
    }
int lca(int u,int v){
    if(h[u]<h[v])swap(u,v);
    for(int i=lg2;i>=0;i--){
        if(h[u]-h[v]>=(1<<i))
        u=P[u][i];
    }
    if(u==v){
        return u;
    }
    for(int i=lg2;i>=0;i--){
        if(P[u][i]!=P[v][i]){
            u=P[u][i];
            v=P[v][i];
        }
    }
    return P[u][0];
}
bool cmp(int x,int y)
{
    return tin[x]<tin[y];
}
void DFS(int u)
{
    for(ii v:e[u])
    {
        DFS(v.fi);
    //    cout<<u<<" "<<v.fi<<" "<<min(dp[u][0]+dp[v.fi][1]+v.se,dp[u][1]+dp[v.fi][0]+v.se)<<'\n';
        ans=min({ans,dp[u][0]+dp[v.fi][1]+v.se,dp[u][1]+dp[v.fi][0]+v.se});
        for(int i=0;i<=1;i++)dp[u][i]=min(dp[v.fi][i]+v.se,dp[u][i]);
    }
}
void Init(int N,int A[],int B[],int D[])
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        int u=A[i],v=B[i],d=D[i];
        u++;
        v++;
        a[u].push_back({v,d});
        a[v].push_back({u,d});
    }
    pre(1,-1);
    build_lca();
    for(int i=1;i<=n;i++)dp[i][0]=dp[i][1]=1e18;
}
ll Query(int S,int X[],int T,int Y[])
{
    vector<int>b,tmp,st;
        ans=1e18;
        int s=S,t=T;
        for(int i=0;i<s;i++)
        {
            int x=X[i];
            x++;
            b.push_back(x);
            d[x]=1;
            dp[x][0]=0;
        }
        for(int i=0;i<t;i++)
        {
            int x=Y[i];
            x++;
            b.push_back(x);
            d[x]=1;
            dp[x][1]=0;
        }
        sort(b.begin(),b.end(),cmp);
        for(int i=1;i<b.size();i++)
        {
            int lc=lca(b[i],b[i-1]);
            if(!d[lc])
            {
                d[lc]=1;
                tmp.push_back(lc);
            }
        }
        for(int x:tmp)b.push_back(x);
        sort(b.begin(),b.end(),cmp);
        st.push_back(b[0]);
        for(int i=1;i<b.size();i++)
        {
            while(tout[st.back()]<tout[b[i]])st.pop_back();
         //   cout<<st.back()<<" "<<b[i]<<'\n';
            e[st.back()].push_back({b[i],dist[b[i]]-dist[st.back()]});
            st.push_back(b[i]);
        }
       // cout<<b[0]<<'\n';
        DFS(b[0]);
        for(int x:b)
        {
            e[x].clear();
            dp[x][0]=dp[x][1]=1e18;
            d[x]=0;
        }
        b.clear();
        tmp.clear();
        st.clear();
        return ans;
}

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