oj.uz

Submission #387940

# Submission time Handle Problem Language Result Execution time Memory
387940 2021-04-09T14:29:01 Z maksim1744 Factories (JOI14_factories) C++17
100 / 100
 4456 ms 197716 KB 
/*
    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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 716 KB Output is correct
2 Correct 1186 ms 9856 KB Output is correct
3 Correct 1260 ms 9808 KB Output is correct
4 Correct 1210 ms 9972 KB Output is correct
5 Correct 1064 ms 10116 KB Output is correct
6 Correct 919 ms 9668 KB Output is correct
7 Correct 1259 ms 9900 KB Output is correct
8 Correct 1212 ms 9992 KB Output is correct
9 Correct 1063 ms 10120 KB Output is correct
10 Correct 915 ms 9784 KB Output is correct
11 Correct 1260 ms 9892 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Output is correct
2 Correct 2450 ms 167084 KB Output is correct
3 Correct 2606 ms 170444 KB Output is correct
4 Correct 1996 ms 167908 KB Output is correct
5 Correct 2443 ms 197716 KB Output is correct
6 Correct 2875 ms 170648 KB Output is correct
7 Correct 2440 ms 40372 KB Output is correct
8 Correct 1666 ms 40048 KB Output is correct
9 Correct 1838 ms 43692 KB Output is correct
10 Correct 2488 ms 40464 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 716 KB Output is correct
2 Correct 1186 ms 9856 KB Output is correct
3 Correct 1260 ms 9808 KB Output is correct
4 Correct 1210 ms 9972 KB Output is correct
5 Correct 1064 ms 10116 KB Output is correct
6 Correct 919 ms 9668 KB Output is correct
7 Correct 1259 ms 9900 KB Output is correct
8 Correct 1212 ms 9992 KB Output is correct
9 Correct 1063 ms 10120 KB Output is correct
10 Correct 915 ms 9784 KB Output is correct
11 Correct 1260 ms 9892 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 2450 ms 167084 KB Output is correct
14 Correct 2606 ms 170444 KB Output is correct
15 Correct 1996 ms 167908 KB Output is correct
16 Correct 2443 ms 197716 KB Output is correct
17 Correct 2875 ms 170648 KB Output is correct
18 Correct 2440 ms 40372 KB Output is correct
19 Correct 1666 ms 40048 KB Output is correct
20 Correct 1838 ms 43692 KB Output is correct
21 Correct 2488 ms 40464 KB Output is correct
22 Correct 4019 ms 169976 KB Output is correct
23 Correct 3835 ms 170616 KB Output is correct
24 Correct 4286 ms 172688 KB Output is correct
25 Correct 4275 ms 174124 KB Output is correct
26 Correct 4456 ms 173256 KB Output is correct
27 Correct 3683 ms 193976 KB Output is correct
28 Correct 3010 ms 171532 KB Output is correct
29 Correct 4292 ms 172972 KB Output is correct
30 Correct 4252 ms 172120 KB Output is correct
31 Correct 4241 ms 172980 KB Output is correct
32 Correct 2024 ms 47460 KB Output is correct
33 Correct 1690 ms 45444 KB Output is correct
34 Correct 2342 ms 39092 KB Output is correct
35 Correct 2272 ms 39080 KB Output is correct
36 Correct 2551 ms 39664 KB Output is correct
37 Correct 2589 ms 39672 KB Output is correct