oj.uz

Submission #944644

# Submission time Handle Problem Language Result Execution time Memory
944644 2024-03-13T02:27:47 Z aufan Factories (JOI14_factories) C++17
0 / 100
 20 ms 66396 KB 
#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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 66396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 66184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 66396 KB Output isn't correct
2 Halted 0 ms 0 KB -