Submission #638133

#	Time	Username	Problem	Language	Result	Execution time	Memory
638133		PoonYaPat	Factories (JOI14_factories)	C++14	100 / 100	6190 ms	222252 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

vector<pii> adj[500001];
int par[500001],level[500001],p[500001][20],sz[500001];
ll dis[500001][20],d[500001],fact[500001];
bool mark[500001];

void dfs(int x, int parent) {
    p[x][0]=parent;
    level[x]=level[parent]+1;
    for (int i=1; i<20; ++i) {
        p[x][i]=p[p[x][i-1]][i-1];
    }

    for (auto s : adj[x]) {
        if (s.first==parent) continue;
        d[s.first]=d[x]+s.second;
        dfs(s.first,x);
    }
}

int lca(int x, int y) {
    if (level[x]<level[y]) swap(x,y);
    int dif=level[x]-level[y];
    for (int i=0; i<20; ++i) {
        if (dif&(1<<i)) x=p[x][i];
    }

    if (x==y) return x;

    for (int i=19; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}

ll dist(int x, int y) {
    return d[x]+d[y]-2*d[lca(x,y)];
}

int dfs_sz(int x, int parent) {
    int cnt=1;
    for (auto s : adj[x]) {
        if (s.first==parent || mark[s.first]) continue;
        cnt+=dfs_sz(s.first,x);
    }
    sz[x]=cnt;
    return cnt;
}

int find_cen(int x, int parent, int cnt) {
    for (auto s : adj[x]) {
        if (!mark[s.first] && s.first!=parent && sz[s.first]>cnt/2) return find_cen(s.first,x,cnt);
    }
    return x;
}

int decompose(int x, int parent) {
    int centroid=find_cen(x,x,dfs_sz(x,x));
    mark[centroid]=true;
    par[centroid]=parent;

    for (auto s : adj[centroid]) {
        if (!mark[s.first]) decompose(s.first,centroid);
    }

    return centroid;
}

void make_dis(int n) {
    for (int i=0; i<n; ++i) {
        int idx=0,m=i;
        while (m!=-1) {
            dis[i][idx++]=dist(i,m);
            m=par[m];
        }
    }
}

void add(int x) {
    int m=x,idx=0;
    while (m!=-1) {
        fact[m]=min(fact[m],dis[x][idx++]);
        m=par[m];
    }
}

ll find(int x) {
    int idx=0,m=x;
    ll mmin=1e15;
    while (m!=-1) {
        mmin=min(mmin,fact[m]+dis[x][idx++]);
        m=par[m];
    }
    return mmin;
}

void clear(int x) {
    while (x!=-1) {
        fact[x]=1e15;
        x=par[x];
    }
}

void Init(int n, int A[], int B[], int D[]) {
    for (int i=0; i<n-1; ++i) {
        adj[A[i]].push_back(pii(B[i],D[i]));
        adj[B[i]].push_back(pii(A[i],D[i]));
    }
    for (int i=0; i<n; ++i) fact[i]=1e15;
    dfs(0,-1); //root is 0
    decompose(0,-1);
    make_dis(n);
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; ++i) add(X[i]);
    ll ans=1e15;
    for (int i=0; i<T; ++i) ans=min(ans,find(Y[i]));
    for (int i=0; i<S; ++i) clear(X[i]);
    return ans;
}

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