Submission #712972

#	Time	Username	Problem	Language	Result	Execution time	Memory
712972		JJAnawat	Factories (JOI14_factories)	C++17	100 / 100	7944 ms	231476 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll inf=1e18;

int n;
vector<pair<int,ll>> g[500005];
int sz[500005],pac[500005];
bitset<500005> rm(0);
int lv[500005],dp[500005][20];
ll dis[500005][20],dlv[500005],mn[500005];

int szdfs(int u,int p){
    sz[u]=1;
    for(auto [v,w]:g[u]){
        if(v==p||rm[v])
            continue;
        sz[u]+=szdfs(v,u);
    }
    return sz[u];
}

int centroid(int u,int p,int ts){
    for(auto [v,w]:g[u]){
        if(v==p||rm[v])
            continue;
        if(sz[v]*2>ts)
            return centroid(v,u,ts);
    }
    return u;
}

void build(int u,int p=0){
    u=centroid(u,0,szdfs(u,0));
    pac[u]=p;
    rm[u]=1;
    for(auto [v,w]:g[u]){
        if(v==p||rm[v])
            continue;
        build(v,u);
    }
}

void pre(int u,int p=0,int l=0,ll d=0){
    dp[u][0]=p;
    lv[u]=l;
    dlv[u]=d;
    for(auto [v,w]:g[u]){
        if(v==p)
            continue;
        pre(v,u,l+1,d+w);
    }
}

int lca(int a,int b){
    if(lv[a]<lv[b])
        swap(a,b);
    for(int i=19;i>=0;i--){
        if(lv[dp[a][i]]>=lv[b])
            a=dp[a][i];
    }
    if(a==b)
        return a;
    for(int i=19;i>=0;i--){
        if(dp[a][i]!=dp[b][i])
            a=dp[a][i],b=dp[b][i];
    }
    return dp[a][0];
}

ll dist(int a,int b){
    return dlv[a]+dlv[b]-2*dlv[lca(a,b)];
}

void upd(int i,bool t){
    int u=i,k=0;
    while(u){
        if(t)
            mn[u]=min(mn[u],dis[i][k]);
        else
            mn[u]=inf;
        u=pac[u];
        k++;
    }
}

ll qr(int i){
    int u=i,k=0;
    ll res=inf;
    while(u){
        res=min(res,mn[u]+dis[i][k]);
        //cout << mn[u] << " " << dis[i][k] << "\n\n";
        u=pac[u];
        k++;
    }
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for(int i=0;i<n-1;i++){
        g[A[i]+1].push_back({B[i]+1,D[i]});
        g[B[i]+1].push_back({A[i]+1,D[i]});
    }
    build(1,0);
    pre(1);
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            dp[i][j]=dp[dp[i][j-1]][j-1];
    for(int i=1;i<=n;i++){
        int u=i,k=0;
        while(u){
            dis[i][k]=dist(i,u);
            //cout << dis[i][k] << " ";
            k++;
            u=pac[u];
        }
        //cout << "\n";
    }
    for(int i=1;i<=n;i++)
        mn[i]=inf;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++)
        upd(X[i]+1,1);
    ll ans=inf;
    for(int i=0;i<T;i++)
        ans=min(ans,qr(Y[i]+1));
    for(int i=0;i<S;i++)
        upd(X[i]+1,0);
    return ans;
}

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