Submission #730591

#	Time	Username	Problem	Language	Result	Execution time	Memory
730591		t6twotwo	Factories (JOI14_factories)	C++17	100 / 100	6040 ms	225668 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> p, dep, euler, P, lg;
vector<int64_t> dis, best;
vector<vector<int>> st;
vector<vector<pair<int, int>>> adj;
constexpr int64_t inf = 1E18;
int F(int x, int y) {
    return dep[x] < dep[y] ? x : y;
}
int lca(int x, int y) {
    if (x == y) {
        return x;
    }
    if (P[x] > P[y]) {
        swap(x, y);
    }
    int z = lg[P[y] - P[x] + 1];
    return F(st[P[x]][z], st[P[y] + 1 - (1 << z)][z]);
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    p.resize(N);
    P.resize(N);
    dis.resize(N);
    dep.resize(N);
    adj.resize(N);
    best.resize(N, inf);
    lg.resize(2 * N + 1);
    for (int i = 2; i <= 2 * N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    st = vector(2 * N - 1, vector<int>(lg[2 * N - 1] + 1, -1));
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    auto dfs = [&](auto dfs, int x, int p) -> void {
        P[x] = euler.size();
        euler.push_back(x);
        for (auto [y, z] : adj[x]) {
            if (y == p) {
                continue;
            }
            dep[y] = dep[x] + 1;
            dis[y] = dis[x] + z;
            dfs(dfs, y, x);
            euler.push_back(x);
        }
    };
    dfs(dfs, 0, -1);
    for (int i = 0; i < 2 * N - 1; i++) {
        st[i][0] = euler[i];
    }
    for (int j = 0; j < lg[2 * N - 1]; j++) {
        for (int i = 0; i + (2 << j) < 2 * N; i++) {
            st[i][j + 1] = F(st[i][j], st[i + (1 << j)][j]);
        }
    }
    vector<bool> vis(N);
    vector<int> sz(N);
    auto init = [&](auto init, int x, int p) -> void {
        sz[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y]) {
                continue;
            }
            init(init, y, x);
            sz[x] += sz[y];
        }
    };
    auto find = [&](auto find, int x, int p, int s) -> int {
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y] || sz[y] * 2 <= s) {
                continue;
            }
            return find(find, y, x, s);
        }
        return x;
    };
    auto cd = [&](auto cd, int x) -> int {
        init(init, x, -1);
        x = find(find, x, -1, sz[x]);
        vis[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (vis[y]) {
                continue;
            }
            p[cd(cd, y)] = x;
        }
        return x;
    };
    p[cd(cd, 0)] = -1;
}
int64_t dist(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[lca(x, y)];
}
long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int x = X[i];
        while (x != -1) {
            best[x] = min(best[x], dist(x, X[i]));
            x = p[x];
        }
    }
    auto ans = inf;
    for (int i = 0; i < T; i++) {
        int x = Y[i];
        while (x != -1) {
            ans = min(ans, best[x] + dist(x, Y[i]));
            x = p[x];
        }
    }
    for (int i = 0; i < S; i++) {
        int x = X[i];
        while (x != -1) {
            best[x] = inf;
            x = p[x];
        }
    }
    return ans;
}

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