Submission #52747

#	Time	Username	Problem	Language	Result	Execution time	Memory
52747		Smelskiy	Factories (JOI14_factories)	C++14	100 / 100	5502 ms	377448 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;







int n;
int timer;
int x,y;
long long depth[500005];
int dp[500005][22];
long long len[500005][22];
int depth2[500005];
vector<pair<int,long long> > v[500005];
long long dp2[500005];
int pred[500005];
int tin[500005];
int tout[500005];
bool used[500005];
int sz;
int q[500005];
long long ans;

void dfs(int x,int y) {
    tin[x]=++timer;
    dp[x][0]=y;
    for (int i=1;i<=19;++i)
        dp[x][i]=dp[dp[x][i-1]][i-1];
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y) continue;
        depth[to]=depth[x];
        depth[to]+=v[x][i].second;
        dfs(to,x);
    }
    tout[x]=timer;
}

int cnt[500005];
int mx[500005];


void dfs1(int x,int y) {
    q[++sz]=x;
    cnt[x]=1;
    mx[x]=0;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y || used[to]) continue;
        dfs1(to,x);
        cnt[x]+=cnt[to];
        if (cnt[to]>mx[x]) {
            mx[x]=cnt[to];
        }
    }
}

void dfs3(int x,int y,long long l,int z) {
    len[x][z]=l;
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (to==y || used[to]) continue;
        dfs3(to,x,l+v[x][i].second,z);
    }
}

void build(int x,int y) {
    sz=0;
    dfs1(x,0);
    int mn=1e9;
    int c=x,xx;
    int cur;
    for (int i=1;i<=sz;++i) {
        xx=q[i];
        cur=max(mx[xx],cnt[x]-cnt[xx]);
        if (cur<mn) {
            mn=cur;
            c=xx;
        }
    }
    used[c]=true;
    x=c;
    pred[x]=y;
    depth2[x]=depth2[y]+1;
    dfs3(x,0,0,depth2[x]);
    for (int i=0;i<v[x].size();++i) {
        int to=v[x][i].first;
        if (!used[to]) build(to,x);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    int z;
    for (int i=0;i<n-1;++i) {
        x=A[i];
        y=B[i];
        ++x; ++y;
        z=D[i];
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    dfs(1,0);
    build(1,0);
    for (int i=1;i<=n;++i)
        dp2[i]=1e15;
}

bool f_pred(int x,int y) {
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}

inline int get_lca(int x,int y) {
    if (f_pred(x,y)) return x;
    if (f_pred(y,x)) return y;
    for (int i=19;i>=0;--i)
        if (dp[x][i] && !f_pred(dp[x][i],y)) x=dp[x][i];
    return dp[x][0];
}

inline long long get_dist(int x,int y) {
    return len[x][depth2[y]];
}

inline void update1(int x) {
    int y=x;
    long long xx;
    while (y) {
        xx=get_dist(x,y);
        if (xx<dp2[y]) dp2[y]=xx;
        y=pred[y];
    }
}
inline void update2(int x) {
    while (x) {
        if (dp2[x]==1e15) return;
        dp2[x]=1e15;
        x=pred[x];
    }
}
inline void solve(int x) {
    int y=x;
    long long xx;
    while (y) {
        xx=get_dist(x,y)+dp2[y];
        if (xx<ans) ans=xx;
        y=pred[y];
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    ans=1e18;
    int x;
    for (int i=0;i<S;++i) {
        x=X[i];
        ++x;
        update1(x);
    }
    for (int i=0;i<T;++i) {
        x=Y[i];
        ++x;
        solve(x);
    }
    for (int i=-0;i<S;++i) {
        x=X[i];
        ++x;
        update2(x);
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs3(int, int, long long int, int)':
factories.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~
factories.cpp: In function 'void build(int, int)':
factories.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();++i) {
                  ~^~~~~~~~~~~~

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