Submission #944799

#	Time	Username	Problem	Language	Result	Execution time	Memory
944799		aufan	Factories (JOI14_factories)	C++17	100 / 100	3934 ms	287400 KiB

factories

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

using namespace std;

const long long INFF = 1e18;

int dep[500000], par[500000], tin[500000], sz[500000], rem[500000], lgg[1000001], pw[20];
long long d[500000], ans[500000];
pair<int, int> sp[20][1000000];
vector<pair<int, int>> g[500000];

void Init(int n, int A[], int B[], int D[]) {
    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]});
    }

    for (int i = 1; i <= 1000000; i++) {
        lgg[i] = __lg(i);
    }
    
    for (int j = 0; j < 20; j++) {
        pw[j] = 1 << j;
    }

    int tim = 0;

    function<void(int, int)> dfs = [&](int x, int pr) {
        sp[0][tim] = {dep[x], x};
        tin[x] = tim++;

        for (auto [z, c] : g[x]) {
            if (z == pr) continue;

            dep[z] = dep[x] + 1;
            d[z] = d[x] + c;

            dfs(z, x);

            sp[0][tim++] = {dep[x], x};
        }
    };

    dep[0] = 0;
    d[0] = 0;
    dfs(0, 0);

    for (int i = 0; i < n; i++) ans[i] = INFF;

    for (int j = 1; (1 << j) <= tim; j++) {
        for (int i = 0; i + (1 << j) - 1 < tim; i++) {
            sp[j][i] = min(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
        }
    }

    function<void(int, int)> compute_subtree = [&](int x, int p) {
        sz[x] = 1;

        for (auto [z, c] : g[x]) {
            if (z == p || rem[z]) continue;

            compute_subtree(z, x);

            sz[x] += sz[z];
        }
    };

    auto get_centroid = [&](int x) {
        compute_subtree(x, -1);

        int tree_size = sz[x];
        bool found = 0;
        while (!found) {
            found = 1;
            for (auto [z, c] : g[x]) {
                if (rem[z] || sz[z] > sz[x]) continue;

                if (sz[z] > tree_size / 2) {
                    x = z;
                    found = 0;
                }
            }
        }

        return x;
    };

    function<int(int)> build_centroid_tree = [&](int x) {
        x = get_centroid(x);
        rem[x] = 1;

        for (auto [z, c] : g[x]) {
            if (rem[z]) continue;

            z = build_centroid_tree(z);

            par[z] = x;
        }

        return x;
    };

    int rt = build_centroid_tree(0);
    par[rt] = -1;
}

int lca(int x, int y) {
    x = tin[x]; y = tin[y];
    if (x > y) swap(x, y);

    int j = lgg[y - x + 1];
    return min(sp[j][x], sp[j][y - pw[j] + 1]).second;
}

long long dist(int x, int y) {
    return d[x] + d[y] - 2 * d[lca(x, y)];
}

void update(int x) {
    int z = x;
    while (z != -1) {
        ans[z] = min(ans[z], dist(z, x));
        z = par[z];
    }
}

long long query(int x) {
    int z = x;
    long long res = INFF;
    while (z != -1) {
        res = min(res, ans[z] + dist(z, x));
        z = par[z];
    }

    return res;
}

void reset(int x) {
    int z = x;
    while (z != -1) {
        ans[z] = INFF;
        z = par[z];
    }
}

long long Query(int x, int a[], int y, int b[]) {
    for (int i = 0; i < x; i++) {
        update(a[i]);
    }

    long long ans = INFF;
    for (int i = 0; i < y; i++) {
        ans = min(ans, query(b[i]));
    }

    for (int i = 0; i < x; i++) {
        reset(a[i]);
    }

    return ans;
}

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