Submission #1309597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309597		hssaan_arif	Factories (JOI14_factories)	C++20	100 / 100	3855 ms	331492 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<ll> used , Dis[N];
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 dist(ll v , ll par , ll di){

    for (auto u : lis[v]){
        if (u.fi != par && !dead[u.fi]){
            dist(u.fi , v , di + u.se);
        }
    }

    Dis[v].pb(di);
}

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

    P[c] = par;
    dead[c] = 1;
    dist(c , par , 0);

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



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

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

ll cal(int v , int 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);

    for (int i=1 ; i<=n ; i++){
        reverse(Dis[i].begin() , Dis[i].end());
    }

}

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,0);
  }
  for (ll i=0 ; i<T ; i++){
    upd1(Y[i]+1 ,Y[i]+1,0);
  }

  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: 67 / 67