Submission #1279202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279202		hiepsimauhong	Factories (JOI14_factories)	C++20	100 / 100	7008 ms	180644 KiB

factories

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

#define FOR(i, L, R) for (long long i = (long long)(L); i <= (long long)(R); ++i)
#define FOD(i, R, L) for (long long i = (long long)(R); i >= (long long)(L); --i)
#define FOA(x, A) for (auto &x : (A))
#define fs first
#define sd second
#define ii pair<long long, long long>

const long long N = 500000 + 5;
const long long oo = (long long)1e18;

vector<ii> g[N];
long long n;

// ---------------- LCA ----------------
struct LCA {
    long long up[N][21];
    long long h[N];
    long long high[N];

    void build(long long u, long long par) {
        FOA(e, g[u]) {
            long long v = e.fs, w = e.sd;
            if (v == par) continue;
            h[v] = h[u] + 1;
            high[v] = high[u] + w;
            up[v][0] = u;
            FOR(i, 1, 20) up[v][i] = up[up[v][i - 1]][i - 1];
            build(v, u);
        }
    }

    long long get(long long u, long long v) {
        if (h[v] < h[u]) swap(u, v);
        long long diff = h[v] - h[u];
        FOR(i, 0, 20) if (diff >> i & 1) v = up[v][i];
        if (u == v) return u;
        FOD(i, 20, 0) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }

    long long path(long long u, long long v) {
        long long w = get(u, v);
        return high[u] + high[v] - 2 * high[w];
    }
} lca;

// ---------------- Centroid Decomposition ----------------
namespace Centroid {
    long long sz[N], parent[N];
    bool cen[N];
    long long nearCen[N];

    void DFS_sz(long long u, long long par) {
        sz[u] = 1;
        FOA(e, g[u]) {
            long long v = e.fs;
            if (v == par || cen[v]) continue;
            DFS_sz(v, u);
            sz[u] += sz[v];
        }
    }

    long long find_centroid(long long u, long long par, long long total) {
        FOA(e, g[u]) {
            long long v = e.fs;
            if (v == par || cen[v]) continue;
            if (sz[v] > total / 2) return find_centroid(v, u, total);
        }
        return u;
    }

    void build_tree(long long u, long long par) {
        DFS_sz(u, -1);
        long long c = find_centroid(u, -1, sz[u]);
        cen[c] = true;
        parent[c] = par;
        FOA(e, g[c]) {
            long long v = e.fs;
            if (!cen[v]) build_tree(v, c);
        }
    }

    void update(long long u) {
        long long v = u;
        while (v) {
            nearCen[v] = min(nearCen[v], lca.path(u, v));
            v = parent[v];
        }
    }

    void clear_node(long long u) {
        long long v = u;
        while (v) {
            nearCen[v] = oo;
            v = parent[v];
        }
    }

    long long query(long long u) {
        long long v = u;
        long long res = oo;
        while (v) {
            res = min(res, nearCen[v] + lca.path(u, v));
            v = parent[v];
        }
        return res;
    }

    void init_all() {
        FOR(i, 1, n) {
            sz[i] = 0;
            parent[i] = 0;
            cen[i] = false;
            nearCen[i] = oo;
        }
    }
}  // namespace Centroid

using namespace Centroid;

// ---------------- API for the grader ----------------
void Init(int _N, int A[], int B[], int D[]) {
    n = _N;
    FOR(i, 1, n) g[i].clear();

    FOR(i, 0, n - 2) {
        long long u = A[i] + 1;
        long long v = B[i] + 1;
        long long w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    // build LCA
    lca.up[1][0] = 0;
    lca.h[1] = 0;
    lca.high[1] = 0;
    lca.build(1, 0);

    // build centroid tree
    init_all();
    build_tree(1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    long long ans = oo;
    vector<long long> leftNodes;

    FOR(i, 0, S - 1) {
        long long u = X[i] + 1;
        leftNodes.push_back(u);
        update(u);
    }

    FOR(i, 0, T - 1) {
        long long u = Y[i] + 1;
        ans = min(ans, query(u));
    }

    FOA(x, leftNodes) clear_node(x);
    return ans;
}

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