제출 #390064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
390064		KoD	공장들 (JOI14_factories)	C++17	100 / 100	4460 ms	152444 KiB

factories

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

template <class T>
using Vec = std::vector<T>;

using ll = long long;

constexpr ll INF = std::numeric_limits<ll>::max() / 2;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    } 
};

int N;
Vec<Vec<std::pair<int, ll>>> graph;
Vec<int> in, depth, col;
Vec<ll> length;
std::array<Vec<int>, 20> parent;

void Init(int V, int A[], int B[], int D[]) {
    N = V;
    graph.resize(V);
    in.resize(V);
    depth.resize(V);
    col.resize(V);
    length.resize(V);
    for (auto& v: parent) {
        v.resize(V);
    }
    for (int i = 0; i < V - 1; ++i) {
        graph[A[i]].emplace_back(B[i], D[i]);
        graph[B[i]].emplace_back(A[i], D[i]);
    }
    int time = 0;
    RecLambda([&](auto&& dfs, const int u, const int p, const int d, const ll l) -> void {
        in[u] = time++;
        depth[u] = d;
        length[u] = l;
        parent[0][u] = p;
        for (const auto [v, c]: graph[u]) {
            if (v != p) {
                dfs(v, u, d + 1, l + c);
            }
        }
    })(0, 0, 0, 0);
    for (int i = 0; i < 19; ++i) {
        for (int j = 0; j < V; ++j) {
            parent[i + 1][j] = parent[i][parent[i][j]];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        std::swap(u, v);
    }
    const auto dif = depth[u] - depth[v];
    for (int i = 0; i < 20; ++i) {
        if (dif >> i & 1) {
            u = parent[i][u];
        }
    }
    if (u == v) {
        return u;
    }
    for (int i = 19; i >= 0; --i) {
        if (parent[i][u] != parent[i][v]) {
            u = parent[i][u];
            v = parent[i][v];
        }
    }
    return parent[0][u];
}

struct Node {
    int uid;
    int idx;
    int pidx;
    int chcnt;
};

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        col[X[i]] = 1;
    }
    for (int i = 0; i < T; ++i) {
        col[Y[i]] = 2;
    }

    Vec<Node> node;
    const auto add_node = [&](const int u) {
        const auto idx = (int) node.size();
        node.push_back(Node { u, idx, idx, 0 });
        return idx;
    };

    Vec<int> vs;
    vs.reserve(S + T);
    for (int i = 0; i < S; ++i) {
        vs.push_back(X[i]);
    }
    for (int i = 0; i < T; ++i) {
        vs.push_back(Y[i]);
    }
    std::sort(vs.begin(), vs.end(), [&](const int u, const int v) {
        return in[u] < in[v];
    });

    std::stack<int> stack;
    for (const auto u: vs) {
        if (stack.empty()) {
            stack.push(add_node(u));
            continue;
        }
        const auto v = node[stack.top()].uid;
        const auto w = lca(u, v);
        int poped = -1;
        while (!stack.empty() and depth[node[stack.top()].uid] > depth[w]) {
            poped = stack.top();
            stack.pop();
        }
        if (stack.empty() or node[stack.top()].uid != w) {
            const auto i = add_node(w);
            if (!stack.empty()) {
                node[i].pidx = stack.top();
            }
            stack.push(i);
        }
        const auto pi = stack.top();
        if (poped != -1) {
            node[poped].pidx = pi;
        }
        const auto i = add_node(u);
        node[i].pidx = pi;
        stack.push(i);
    }

    const auto size = (int) node.size();
    for (int i = 0; i < size; ++i) {
        if (node[i].pidx != i) {
            node[node[i].pidx].chcnt += 1;
        }
    }
    std::queue<int> que;
    for (int i = 0; i < size; ++i) {
        if (node[i].chcnt == 0) {
            que.push(i);
        }
    }

    Vec<ll> black(size, INF), white(size, INF);
    ll ans = INF;
    while (!que.empty()) {
        const auto i = que.front();
        que.pop();
        if (col[node[i].uid] == 1) {
            black[i] = 0;
        }
        if (col[node[i].uid] == 2) {
            white[i] = 0;
        }
        ans = std::min(ans, black[i] + white[i]);
        const auto pi = node[i].pidx;
        if (pi != i) {
            const auto len = length[node[i].uid] - length[node[pi].uid];
            black[pi] = std::min(black[pi], black[i] + len);
            white[pi] = std::min(white[pi], white[i] + len);
            node[pi].chcnt -= 1;
            if (node[pi].chcnt == 0) {
                que.push(pi);
            }
        }
    }

    for (int i = 0; i < S; ++i) {
        col[X[i]] = 0;
    }
    for (int i = 0; i < T; ++i) {
        col[Y[i]] = 0;
    }

    return ans;
}

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