oj.uz

Submission #712970

# Submission time Handle Problem Language Result Execution time Memory
712970 2023-03-20T16:57:31 Z JJAnawat Factories (JOI14_factories) C++17
0 / 100
 23 ms 25080 KB 
#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);
    }
}

int 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]);
        u=pac[u];
        k++;
    }
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i=1;i<n;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);
            k++;
            u=pac[u];
        }
    }
    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,0);
    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,1);
    return ans;
}

Compilation message

factories.cpp: In function 'int pre(int, int, int, ll)':
factories.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 25080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 24448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 25080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -