oj.uz

Submission #387936

# Submission time Handle Problem Language Result Execution time Memory
387936 2021-04-09T14:26:49 Z maksim1744 Factories (JOI14_factories) C++17
100 / 100
 5484 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 = dist(u, v);
                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 684 KB Output is correct
2 Correct 1218 ms 9880 KB Output is correct
3 Correct 1302 ms 9792 KB Output is correct
4 Correct 1244 ms 9892 KB Output is correct
5 Correct 1077 ms 10060 KB Output is correct
6 Correct 928 ms 9784 KB Output is correct
7 Correct 1279 ms 9740 KB Output is correct
8 Correct 1259 ms 9860 KB Output is correct
9 Correct 1067 ms 9988 KB Output is correct
10 Correct 933 ms 9688 KB Output is correct
11 Correct 1291 ms 9824 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 2669 ms 167096 KB Output is correct
3 Correct 3086 ms 170404 KB Output is correct
4 Correct 2257 ms 167984 KB Output is correct
5 Correct 2594 ms 197716 KB Output is correct
6 Correct 3282 ms 170628 KB Output is correct
7 Correct 2749 ms 40160 KB Output is correct
8 Correct 1756 ms 39992 KB Output is correct
9 Correct 1847 ms 43656 KB Output is correct
10 Correct 2679 ms 40512 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 684 KB Output is correct
2 Correct 1218 ms 9880 KB Output is correct
3 Correct 1302 ms 9792 KB Output is correct
4 Correct 1244 ms 9892 KB Output is correct
5 Correct 1077 ms 10060 KB Output is correct
6 Correct 928 ms 9784 KB Output is correct
7 Correct 1279 ms 9740 KB Output is correct
8 Correct 1259 ms 9860 KB Output is correct
9 Correct 1067 ms 9988 KB Output is correct
10 Correct 933 ms 9688 KB Output is correct
11 Correct 1291 ms 9824 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 2669 ms 167096 KB Output is correct
14 Correct 3086 ms 170404 KB Output is correct
15 Correct 2257 ms 167984 KB Output is correct
16 Correct 2594 ms 197716 KB Output is correct
17 Correct 3282 ms 170628 KB Output is correct
18 Correct 2749 ms 40160 KB Output is correct
19 Correct 1756 ms 39992 KB Output is correct
20 Correct 1847 ms 43656 KB Output is correct
21 Correct 2679 ms 40512 KB Output is correct
22 Correct 4335 ms 169864 KB Output is correct
23 Correct 4030 ms 170648 KB Output is correct
24 Correct 4648 ms 172656 KB Output is correct
25 Correct 4742 ms 174236 KB Output is correct
26 Correct 5484 ms 173288 KB Output is correct
27 Correct 4159 ms 193888 KB Output is correct
28 Correct 3175 ms 171484 KB Output is correct
29 Correct 4825 ms 172876 KB Output is correct
30 Correct 4799 ms 172164 KB Output is correct
31 Correct 4797 ms 172908 KB Output is correct
32 Correct 2021 ms 47312 KB Output is correct
33 Correct 1734 ms 45512 KB Output is correct
34 Correct 2528 ms 39088 KB Output is correct
35 Correct 2433 ms 39048 KB Output is correct
36 Correct 2870 ms 39740 KB Output is correct
37 Correct 2920 ms 39636 KB Output is correct