Submission #1317239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317239		h1drogen	Factories (JOI14_factories)	C++20	100 / 100	2183 ms	269828 KiB

factories

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

const long long INF = 1e18;
const int LOGN = 20; // максимум глубины центроидного дерева
int N;
vector<vector<pair<int,int>>> g;
vector<int> sz, par, us;
vector<long long> dp, best;
vector<int> tin, tout;
int up[LOGN+1][500500];
int tim;

// Предвычисленные расстояния до центроид-предков
vector<vector<long long>> dist_pre;

// ================= 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<=LOGN;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=LOGN;i>=0;i--){
        if(!check(up[i][a],b))
            a = up[i][a];
    }
    return up[0][a];
}

long long dist(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 [to,_]:g[v]){
        if(sz[to]>n/2 && to!=p && !us[to])
            return get(to,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);
    }
}

// ================= Предвычисление dist до центроид-предков =================
void prep_dist(int v){
    int cur = v;
    while(cur >= 0){
        dist_pre[v].push_back(dist(v,cur));
        cur = par[cur];
    }
}

// ================= Обновления и запросы =================
void upd(int v){
    int cur = v;
    int lvl = 0;
    while(cur >= 0){
        best[cur] = min(best[cur], dist_pre[v][lvl]);
        cur = par[cur];
        lvl++;
    }
}

void res(int v, long long &ans){
    int cur = v;
    int lvl = 0;
    while(cur >= 0){
        ans = min(ans, dist_pre[v][lvl] + best[cur]);
        cur = par[cur];
        lvl++;
    }
}

void nulify(int v){
    int cur = v;
    while(cur >= 0){
        best[cur] = INF;
        cur = par[cur];
    }
}

// ================= Батч API =================
void Init(int _N, int A[], int B[], int D[]) {
    N = _N;
    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_pre.assign(N, {});

    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++)
        prep_dist(i); // предвычисляем dist до центроид-предков
}

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

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

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

    return ans;
}

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