제출 #922485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
922485		AlphaMale06	공장들 (JOI14_factories)	C++14	100 / 100	6119 ms	159004 KiB

factories

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back
#define F first
#define S second


const int mxn = 5e5+3;

vector<pair<int, int>> adj[mxn];
int tin[mxn], tout[mxn];
int p[mxn][20];
ll dst[mxn];
int timer = -1;
int sz[mxn];
bool mark[mxn];
int cp[mxn];
ll cendist[mxn];
int en;

void dfs(int v, int par){
    p[v][0]=par;
    tin[v]=++timer;
    dst[v]+=dst[par];
    for(int i=1; i<20; i++){
        p[v][i]=p[p[v][i-1]][i-1];
    }
    for(auto to : adj[v]){
        if(to.F!=par){
            dst[to.F]=to.S;
            dfs(to.F, v);
        }
    }
    tout[v]=timer;
}


bool anc(int u, int v){
    if(tin[u]<=tin[v] && tout[u]>=tout[v])return 1;
    return 0;
}

int lca(int u, int v){
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    for(int i=19; i>=0; i--){
        if(!anc(p[u][i], v))u=p[u][i];
    }
    return p[u][0];
}


ll dist(int u, int v){
    return dst[u]+dst[v]-2*dst[lca(u, v)];
}

void subtreesize(int v, int par){
    sz[v]=1;
    for(auto to : adj[v]){
        if(to.F!=par && !mark[to.F]){
            subtreesize(to.F, v);
            sz[v]+=sz[to.F];
        }
    }
}

int centr(int v, int par, int siz){
    for(auto to : adj[v]){
        if(to.F==par || mark[to.F])continue;
        if(sz[to.F]*2>=siz)return centr(to.F, v, siz);
    }
    return v;
}

void decompose(int v, int par){
    subtreesize(v, par);
    int centroid = centr(v, par, sz[v]);
    mark[centroid]=1;
    if(par!=-1){
        cp[centroid]=par;
    }
    for(auto to : adj[centroid]){
        if(!mark[to.F])decompose(to.F, centroid);
    }
}


void Init(int n, int u[], int v[], int w[]) {
    en=n;
    for(int i=0; i<n-1; i++){
        adj[u[i]].pb({v[i], w[i]});
        adj[v[i]].pb({u[i], w[i]});
    }
    dfs(0, 0);
    for(int i=0; i< n; i++)cp[i]=i;
    decompose(0, -1);
    for(int i=0; i< n; i++)cendist[i]=1e14;
}

long long Query(int sz1, int a[], int sz2, int b[]) {
    for(int i=0; i<sz2; i++){
        int v=b[i];
        cendist[v]=0;
        while(v!=cp[v]){
            v=cp[v];
            cendist[v]=min(cendist[v], dist(b[i], v));
        }
    }
    ll ans=1e18;
    for(int i=0; i<sz1; i++){
        int v=a[i];
        ans=min(ans, cendist[v]+dist(v, a[i]));
        while(v!=cp[v]){
            v=cp[v];
            ans=min(ans, cendist[v]+dist(v, a[i]));
        }
    }
    for(int i=0; i< sz2; i++){
        int v=b[i];
        cendist[v]=1e14;
        while(v!=cp[v]){
            v=cp[v];
            cendist[v]=1e14;
        }
    }
    return ans;
}

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