Submission #387940

#	Time	Username	Problem	Language	Result	Execution time	Memory
387940		maksim1744	Factories (JOI14_factories)	C++17	100 / 100	4456 ms	197716 KiB

factories

/*
    author:  Maksim1744
    created: 09.04.2021 12:06:25
*/
 
#include "bits/stdc++.h"
 
using namespace std;
 
#define ll   long long
#define ld   long double
 
#define mp   make_pair
#define pb   push_back
#define eb   emplace_back
 
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
 
template<typename T>             vector<T>& operator--            (vector<T>& v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T>& v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T>& v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}
 
#ifdef HOME
#define SHOW_COLORS
#include "C:/C++ libs/print.cpp"
#else
#define show(...)     42
#define mclock        42
#define shows         42
#define debug if (false)
#endif
 
vector<int> lca_ind;
vector<vector<int>> lca_sparse;
vector<int> lca_p2;
vector<int> lca_depth;
vector<ll> lca_w_depth;
vector<int> tin, tout;
void build_lca_sparse(vector<vector<pair<int, int>>>& g, int root = 0) {
    int n = g.size();
    vector<int> euler;
    lca_ind.resize(n);
    lca_depth.assign(n, -1);
    lca_w_depth.assign(n, 0);
    tin.resize(n);
    tout.resize(n);
    int timer = 0;
    function<void(int, int)> dfs = [&](int v, int depth) {
        lca_ind[v] = euler.size();
        euler.pb(v);
        tin[v] = timer++;
        lca_depth[v] = depth;
        for (auto [k, w] : g[v]) {
            if (lca_depth[k] == -1) {
                lca_w_depth[k] = lca_w_depth[v] + w;
                dfs(k, depth + 1);
                euler.pb(v);
            }
        }
        tout[v] = timer++;
    };
    dfs(root, 0);
    int m = euler.size();
    int log = 1;
    while ((1 << log) < m)
        ++log;
    lca_sparse.resize(log);
    lca_sparse[0].resize(m);
    lca_p2.resize(m + 1);
    int pp2 = 0;
    for (int i = 1; i < lca_p2.size(); ++i) {
        if (1 << (pp2 + 1) <= i)
            ++pp2;
        lca_p2[i] = pp2;
    }
    lca_p2[0] = 0;
    for (int i = 0; i < m; ++i)
        lca_sparse[0][i] = euler[i];
    for (int i = 1; i < log; ++i) {
        lca_sparse[i].assign(m, 0);
        for (int j = 0; j < m - (1 << (i - 1)); ++j) {
            int v1 = lca_sparse[i - 1][j], v2 = lca_sparse[i - 1][j + (1 << (i - 1))];
            if (lca_depth[v1] < lca_depth[v2])
                lca_sparse[i][j] = v1;
            else
                lca_sparse[i][j] = v2;
        }
    }
}
 
int get_lca(int u, int v) {
    if (u == v)
        return u;
    u = lca_ind[u];
    v = lca_ind[v];
    if (u > v)
        swap(u, v);
    int v1 = lca_sparse[lca_p2[v - u + 1]][u], v2 = lca_sparse[lca_p2[v - u + 1]][v - (1 << lca_p2[v - u + 1]) + 1];
    if (lca_depth[v1] < lca_depth[v2])
        return v1;
    else
        return v2;
}

ll dist(int u, int v) {
    return lca_w_depth[u] + lca_w_depth[v] - 2 * lca_w_depth[get_lca(u, v)];
}
 
vector<pair<ll, ll>> dp;
vector<int> u;
vector<vector<pair<int, ll>>> g0;
vector<ll> dd;
vector<int> tp;
int ustep = 0;
 
void Init(int N, int A[], int B[], int D[]) {
    int n = N;
    g0.resize(n);
    dd.resize(n);
    tp.resize(n);
    dp.resize(n);
    u.assign(n, -1);
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n; ++i) {
        g[A[i]].eb(B[i], D[i]);
        g[B[i]].eb(A[i], D[i]);
    }
    build_lca_sparse(g, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> vert;
    for (int i = 0; i < S; ++i) {
        vert.pb(X[i]);
    }
    for (int i = 0; i < T; ++i) {
        vert.pb(Y[i]);
    }

    sort(vert.begin(), vert.end(), [&](int i, int j) {return tin[i] < tin[j];});
    int sz = vert.size();
    for (int i = 0; i < sz; ++i) {
        vert.pb(get_lca(vert[i], vert[(i + 1) % sz]));
    }
    sort(vert.begin(), vert.end());
    vert.erase(unique(vert.begin(), vert.end()), vert.end());

    vector<pair<int, int>> ev;
    for (int v : vert) {
        ev.eb(tin[v], v);
        ev.eb(tout[v], v);
    }
    sort(ev.begin(), ev.end());
    vector<int> path;
    ll ans = 1e18;

    for (int v : vert)
        tp[v] = 0;
    for (int i = 0; i < S; ++i)
        tp[X[i]] = 1;
    for (int i = 0; i < T; ++i)
        tp[Y[i]] = 2;

    for (auto [tm, v] : ev) {
        if (!path.empty() && path.back() == v) {
            path.pop_back();
        } else {
            if (!path.empty()) {
                int u = path.back();
                ll d = lca_w_depth[v] - lca_w_depth[u];
                g0[u].eb(v, d);
                g0[v].eb(u, d);
            }
            path.pb(v);
        }
    }

    ++ustep;

    function<void(int)> dfs = [&](int v) {
        u[v] = ustep;
        dp[v] = {1e18, 1e18};
        if (tp[v] == 1) dp[v].first = 0;
        else if (tp[v] == 2) dp[v].second = 0;
        for (auto [k, w] : g0[v]) {
            if (u[k] != ustep) {
                dfs(k);
                dp[v].first = min(dp[v].first, dp[k].first + w);
                dp[v].second = min(dp[v].second, dp[k].second + w);
            }
        }
        ans = min(ans, dp[v].first + dp[v].second);
    };
    dfs(vert[0]);
 
    for (int k : vert)
        g0[k].clear();

    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void build_lca_sparse(std::vector<std::vector<std::pair<int, int> > >&, int)':
factories.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 1; i < lca_p2.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~

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