제출 #1309587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309587		hssaan_arif	공장들 (JOI14_factories)	C++20	33 / 100	8098 ms	184612 KiB

factories

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

#define endl "\n"
#define pb push_back
#define ll long long
#define fi first
#define se second

const ll N = 5e5 + 5, M = 1e9 + 7, LG = 20;

ll n , A[N] , sz[N] , P[N] , u , v , sp[N][LG] , Dep[N] , m , H[N] , B[N] ;
int Ne , Q , L[N] , R[N] , D[N] , S , T , X[N] , Y[N];
vector<pair<ll,ll>> lis[N];
vector<int> used;
bool dead[N];

void dfs(ll v , ll par , ll wi){

    Dep[v] = Dep[par] + wi;
    H[v] = H[par] + 1;
    sp[v][0] = par;

    for (auto u : lis[v]){
        if (u.fi == par) continue;
        dfs(u.fi , v , u.se);
    }
}

void pre_dfs(ll v , ll par){
    sz[v] = 1;

    for (auto u : lis[v]){
        if (u.fi == par || dead[u.fi]) continue;
        pre_dfs(u.fi , v);
        sz[v] += sz[u.fi];
    }
}

ll ce(ll v , ll par , ll root){
    for (auto u : lis[v]){
        if (u.fi != par && !dead[u.fi] && 2 * sz[u.fi] > sz[root]) return ce(u.fi , v , root);
    }
    return v;
}

void get(ll v , ll par){
    pre_dfs(v , par);
    ll c = ce(v , par , v);

    P[c] = par;
    dead[c] = 1;

    for (auto u : lis[c]){
        if (!dead[u.fi]) get(u.fi , c);
    }
}

ll dist(ll u , ll v){
    if (H[v] > H[u]){
        swap(u , v);
    }

    ll dif = H[u] - H[v] , u1 = u , v1 = v;

    for (ll i=LG-1 ; i>=0 ; i--){
        if ((1<<i) & dif){
            u = sp[u][i];
        }
    }

    if (u == v){
        return Dep[u1] - Dep[v1];
    }

    for (ll i=LG-1 ; i>=0 ; i--){
        if (sp[u][i] != sp[v][i]){
            u = sp[u][i];
            v = sp[v][i];
        }
    }

    return Dep[u1] + Dep[v1] - 2 * Dep[sp[u][0]]; 
}

void upd(ll v , ll par){
    while(par != -1){
        used.pb(par);
        A[par] = min(A[par] , dist(v , par));
        par = P[par];
    }
}

void upd1(ll v , ll par){
    while(par != -1){
        used.pb(par);
        B[par] = min(B[par] , dist(v , par));
        par = P[par];
    }
}

ll cal(ll v , ll par){
    ll ans = 1e18;

    while(par != -1){
        ans = min(ans , A[par] + B[par]);
        par = P[par];  
    }

    return ans;
}

void Init(int N, int L[], int R[], int D[]) {
    n = N;
    for (int i=1 ; i<=N ; i++){
        lis[i].clear();
    }

    for (ll i=0 ; i<n-1 ; i++){
        u = L[i]+1;
        v = R[i]+1;
        m = D[i];
        lis[u].pb({v,m});
        lis[v].pb({u,m});
    }

    for (ll i=0 ; i<=N ; i++) A[i] = B[i] = 1e18;
    

    dfs(1 , 0 , 0);

    for (ll j=1 ; j<LG ; j++){
        for (ll i=1 ; i<=n ; i++){
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }

    get(1 , -1);

}

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

  ll bs = 1e18;
  for (ll i=0 ; i<T ; i++){
    bs = min(bs , cal(Y[i]+1 ,Y[i]+1));
  }

  for (int i : used){
    A[i] = B[i] = 1e18;
  }
  used.clear();
  return bs;
}

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