제출 #429477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429477		tht2005	공장들 (JOI14_factories)	C++17	33 / 100	8090 ms	130320 KiB

factories

/*
 *  Written by
 *       ______  _   _  ______  ____  ____  ____  ____
 *      |_    _|| |_| ||_    _||_   || __ || __ |/  _/
 *        |  |  |  _  |  |  |    / / ||  ||||  ||| |__
 *        |  |  | | | |  |  |   | |_ ||__||||__||\__  \
 *        |__|  |_| |_|  |__|   |___||____||____|/____/
 */

#include <bits/stdc++.h>
using namespace std;

#define nmax 500050
#define ll long long
#define ii pair<int, int>

const int N = 1 << 20;
const ll inf = 1LL << 50;

template<class T>
struct RMQ
{
    int n;
    T inf;
    T val[N << 1];

    RMQ(T __inf): inf(__inf) {}

    void init(const vector<T>& v)
    {
        int sz = v.size();
        for(int i = 0; i < sz; ++i) val[i + N] = v[i];
        for(int i = sz; i < N; ++i) val[i + N] = inf;
        for(int i = N - 1; i > 0; --i) val[i] = min(val[i<<1], val[i<<1|1]);
    }

    void modify(int p, T v)
    {
        for(val[p += N] = v; p > 1; p >>= 1)
            val[p >> 1] = min(val[p], val[p ^ 1]);
    }

    T get(int l, int r)
    {
        T ans = inf;
        for(l += N, r += N; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ans = min(ans, val[l++]);
            if(r & 1) ans = min(ans, val[--r]);
        }
        return ans;
    }
};

int n, p[nmax], lv[nmax], sz[nmax], r[nmax];
ll depth[nmax], ans[nmax];
RMQ<ii> rmq(ii(INT_MAX, 0));
vector<ii> adj[nmax], lca_tbl;
vector<int> el;

void euler_tour(int u = 0, int p = -1, ll D = 0)
{
    depth[u] = D;
    lv[u] = el.size();
    el.push_back(u);
    for(auto [C, v]: adj[u]) {
        if(v == p) continue;
        euler_tour(v, u, D + C);
        el.push_back(u);
    }
}

inline int lca(int u, int v)
{
    if(lv[u] > lv[v]) swap(u, v);
    return rmq.get(lv[u], lv[v] + 1).second;
}

inline ll dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int dfs(int u, int p = -1)
{
    sz[u] = 1;
    for(auto [C, v]: adj[u]) if(v != p && !r[v]) sz[u] += dfs(v, u);
    return sz[u];
}

int get_centroid(int m, int u, int p = -1)
{
    for(auto [C, v]: adj[u])
        if(v != p && !r[v] && 2 * sz[v] > m) return get_centroid(m, v, u);
    return u;
}

int centroid(int u = 0)
{
    u = get_centroid(dfs(u), u);
    r[u] = 1;
    p[u] = -1;
    for(auto [C, v]: adj[u]) {
        if(!r[v]) p[centroid(v)] = u;
    }
    return u;
}

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n - 1; ++i) {
        adj[A[i]].push_back(ii(D[i], B[i]));
        adj[B[i]].push_back(ii(D[i], A[i]));
    }
    euler_tour();
    for(int i: el)
        lca_tbl.push_back(ii(lv[i], i));
    rmq.init(lca_tbl);
    centroid();
    fill(ans, ans + 1 + n, inf);
}

template<bool undo>
inline void update(int x)
{
    for(int u = x; u != -1; u = p[u]) {
        if(undo) ans[u] = inf;
        else ans[u] = min(ans[u], dist(u, x));
    }
}

inline ll get(int x)
{
    ll res = inf;
    for(int u = x; u != -1; u = p[u])
        res = min(res, ans[u] + dist(u, x));
    return res;
}

ll Query(int S, int X[], int T, int Y[])
{
    ll res = inf;
    for(int i = 0; i < S; ++i)
        update<0>(X[i]);
    for(int i = 0; i < T; ++i)
        res = min(res, get(Y[i]));
    for(int i = 0; i < S; ++i)
        update<1>(X[i]);
    return res;
}

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