제출 #631754

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

factories

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

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpi;

namespace kactl {
template <class T>
struct RMQ {
    vector<vector<T>> jmp;
    void init(const vector<T> &V)
    {
        jmp.resize(1, vector<T>(V));
        for(int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
            jmp.emplace_back(sz(V) - pw * 2 + 1);
            rep(j, 0, sz(jmp[k]))
                jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
        }
    }
    T query(int a, int b)
    {
        assert(a < b); // or return inf if a == b
        int dep = 31 - __builtin_clz(b - a);
        return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
    }
};
struct LCA {
    int T = 0;
    vi time, path, ret;
    vl depth;
    RMQ<int> rmq;
    void init(vector<vpi> &C)
    {
        time.resize(sz(C));
        depth.resize(sz(C));
        dfs(C, 0, -1);
        rmq.init(ret);
    }
    void dfs(vector<vpi> &C, int v, int par)
    {
        time[v] = T++;
        for(auto [y, d] : C[v]) {
            if(y != par) {
                path.push_back(v), ret.push_back(time[v]);
                depth[y] = depth[v] + d;
                dfs(C, y, v);
            }
        }
    }
    int lca(int a, int b)
    {
        if(a == b) return a;
        tie(a, b) = minmax(time[a], time[b]);
        return path[rmq.query(a, b)];
    }
    ll dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
};
vpi compressTree(LCA &lca, const vi &subset)
{
    vi li = subset, &T = lca.time;
    auto cmp = [&](int a, int b) { return T[a] < T[b]; };
    sort(all(li), cmp);
    int m = sz(li) - 1;
    rep(i, 0, m)
    {
        int a = li[i], b = li[i + 1];
        li.push_back(lca.lca(a, b));
    }
    sort(all(li), cmp);
    li.erase(unique(all(li)), li.end());
    vpi ret = {pii(li[0], li[0])};
    rep(i, 0, sz(li) - 1)
    {
        int a = li[i], b = li[i + 1];
        ret.emplace_back(lca.lca(a, b), b);
    }
    return ret;
}
}; // namespace kactl

using namespace kactl;
const int nax = 500123;

ll toX[nax], toY[nax];
vi ch[nax];

#define x first
#define y second

LCA lca;

void Init(int N, int A[], int B[], int D[])
{
    vector<vpi> g(N);
    for(int i = 0; i < N; i++) {
        toX[i] = toY[i] = 1e18;
    }
    for(int i = 0; i < N - 1; i++) {
        g[A[i]].emplace_back(B[i], D[i]);
        g[B[i]].emplace_back(A[i], D[i]);
    }
    lca.init(g);
}

ll ans;

void chmin(ll &a, ll b)
{
    if(a > b) {
        a = b;
    }
}

void dfs(int u)
{
    for(auto to : ch[u]) {
        dfs(to);
        chmin(toX[u], toX[to] + lca.dist(u, to));
        chmin(toY[u], toY[to] + lca.dist(u, to));
    }
    ans = min(ans, toX[u] + toY[u]);
}

ll Query(int S, int X[], int T, int Y[])
{
    vi s;
    for(int i = 0; i < S; i++) {
        toX[X[i]] = 0;
        s.emplace_back(X[i]);
    }
    for(int i = 0; i < T; i++) {
        toY[Y[i]] = 0;
        s.emplace_back(Y[i]);
    }
    vpi r = compressTree(lca, s);
    for(int i = 1; i < sz(r); i++) {
        ch[r[i].x].emplace_back(r[i].y);
    }
    ans = 1e18;
    dfs(r[0].x);
    for(auto [_, i] : r) {
        toX[i] = toY[i] = 1e18;
        ch[i].clear();
    }
    return ans;
}

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