Submission #1317237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317237		h1drogen	공장들 (JOI14_factories)	C++20	15 / 100	3986 ms	589824 KiB

factories

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

const long long INF = 1e18;
const int NMAX = 500500;

vector<vector<pair<int,int>>> g;           // дерево
vector<int> sz, tin, tout, us, par;       // вспомогательные массивы
vector<long long> dp, best;               // dp и best расстояния
int up[21][NMAX];                          // бинарное поднятие
int tim;
vector<map<int,long long>> dist;           // dist для центроидов
long long ans;

// ======================== DFS и LCA ========================
void dfs(int v,int p,long long sum){
    tin[v] = tim++;
    dp[v] = sum;
    up[0][v] = p;
    for(int i=1;i<=20;i++)
        up[i][v] = up[i-1][up[i-1][v]];
    for(auto [to,c]:g[v]){
        if(to!=p)
            dfs(to,v,sum+c);
    }
    tout[v] = tim;
}

bool check(int a,int b){
    return tin[a]<=tin[b] && tout[b]<=tout[a];
}

int lca(int a,int b){
    if(check(a,b)) return a;
    if(check(b,a)) return b;
    for(int i=20;i>=0;i--){
        if(!check(up[i][a],b))
            a = up[i][a];
    }
    return up[0][a];
}

long long disti(int a,int b){
    return dp[a] + dp[b] - 2*dp[lca(a,b)];
}

// ======================== Центроидное разложение ========================
void precalc(int v,int p){
    sz[v] = 1;
    for(auto [to,_]: g[v]){
        if(to!=p && !us[to]){
            precalc(to,v);
            sz[v] += sz[to];
        }
    }
}

int get(int v,int p,int n){
    for(auto k:g[v]){
        if(sz[k.first] > n/2 && k.first != p && !us[k.first])
            return get(k.first,v,n);
    }
    return v;
}

void build(int v,int p){
    precalc(v,-1);
    int c = get(v,-1,sz[v]);
    us[c] = 1;
    par[c] = p;
    for(auto k:g[c]){
        if(!us[k.first])
            build(k.first,c);
    }
}

// ======================== Обновления и запросы ========================
void upd1(int v,int x){
    dist[x][v] = disti(v,x);
    if(par[v]<0) return;
    upd1(par[v],x);
}

void upd(int v,int x){
    best[v] = min(dist[x][v], best[v]);
    if(par[v]<0) return;
    upd(par[v],x);
}

void nulify(int v,int x){
    best[v] = INF;
    if(par[v]<0) return;
    nulify(par[v],x);
}

void res(int v,int x){
    ans = min(ans, dist[x][v] + best[v]);
    if(par[v]<0) return;
    res(par[v],x);
}

// ======================== Батч API ========================
void Init(int N, int A[], int B[], int D[]) {
    tim = 0;
    g.assign(N, {});
    dp.assign(N,0);
    tin.assign(N,0);
    tout.assign(N,0);
    sz.assign(N,0);
    best.assign(N, INF);
    us.assign(N,0);
    par.assign(N,-1);
    dist.assign(N, map<int,long long>());

    for(int i=0;i<N-1;i++){
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }

    dfs(0,0,0);
    build(0,-1);

    for(int i=0;i<N;i++)
        upd1(i,i);
}

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

    ans = INF;
    for(int i=0;i<T;i++)
        res(Y[i], Y[i]);

    for(int i=0;i<S;i++)
        nulify(X[i], X[i]);

    return ans;
}

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