제출 #1196386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196386		Szil	공장들 (JOI14_factories)	C++20	100 / 100	5508 ms	150668 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int K = 20;
const ll INF = 1e16;

vector<vector<pair<int, ll>>> g;
vector<int> tin, tout, par;
vector<ll> depth, closest;
vector<vector<int>> up;
int timer, n;

void dfs(int u, int p = -1, ll d = 0) {
    tin[u] = timer++;
    depth[u] = d;
    for (auto [v, w] : g[u]) {
        if (v == p) continue;
        up[v][0] = u;
        dfs(v, u, d + w);
    }
    tout[u] = timer++;
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void preprocess_lca() {
    for (int k = 1; k < K; k++) {
        for (int i = 1; i <= n; i++) {
            up[i][k] = up[up[i][k-1]][k-1];
        }
    }
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = K-1; i >= 0; i--) {
        if (up[u][i] && !is_ancestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

ll calc_dist(int u, int v) {
    int x = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[x];
}

void build_centroid_tree() {
    par = vector<int>(n+1);
    vector<int> siz(n+1);
    vector<bool> vis(n+1);

    auto calc_siz = [&](auto &&self, int u, int p = -1) -> void {
        siz[u] = 1;
        for (auto [v, w] : g[u]) {
            if (v == p || vis[v]) continue;
            self(self, v, u);
            siz[u] += siz[v];
        }
    };

    auto find_centroid = [&](auto &&self, int u, int th, int p = -1) -> int {
        for (auto [v, w] : g[u]) {
            if (v == p || vis[v]) continue;
            if (siz[v] > th) return self(self, v, th, u);
        }
        return u;
    };

    auto decomp = [&](auto &&self, int u) -> int {
        calc_siz(calc_siz, u);
        u = find_centroid(find_centroid, u, siz[u]/2);
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                int x = self(self, v);
                par[x] = u;
            }
        }
        return u;
    };

    decomp(decomp, 1);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    g = vector<vector<pair<int, ll>>>(n+1);
    tin = vector<int>(n+1);
    tout = vector<int>(n+1);
    depth = vector<ll>(n+1);
    closest = vector<ll>(n+1, INF);
    up = vector<vector<int>>(n+1, vector<int>(K));
    timer = 1;

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

    dfs(1);
    preprocess_lca();
    build_centroid_tree();
}

long long Query(int S, int X[], int T, int Y[]) {

    // ll ans = INF;
    // for (int i = 0; i < S; i++) {
    //     for (int j = 0; j < T; j++) {
    //         cerr << X[i]+1 << " " << Y[j]+1 << ": " << calc_dist(X[i]+1, Y[j]+1) << endl;
    //         ans = min(ans, calc_dist(X[i]+1, Y[j]+1));
    //     }
    // }


    for (int i = 0; i < S; i++) {
        int u = X[i]+1;
        int v = u;
        while (v) {
            closest[v] = min(closest[v], calc_dist(v, u));
            v = par[v];
        }
    }

    ll ans = INF;
    for (int i = 0; i < T; i++) {
        int u = Y[i]+1;
        int v = u;
        while (v) {
            ans = min(ans, closest[v] + calc_dist(u, v));
            v = par[v];
        }
    }

    for (int i = 0; i < S; i++) {
        int u = X[i]+1;
        int v = u;
        while (v) {
            closest[v] = INF;
            v = par[v];
        }
    }

    return ans;
}

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