oj.uz

Submission #387839

# Submission time Handle Problem Language Result Execution time Memory
387839 2021-04-09T09:23:29 Z maksim1744 Factories (JOI14_factories) C++17
100 / 100
 5642 ms 185900 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<vector<pair<int, ll>>> g0;
vector<ll> dd;

void Init(int N, int A[], int B[], int D[]) {
    int n = N;
    g0.resize(n);
    dd.resize(n);
    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());
    vert.erase(unique(vert.begin(), vert.end()), vert.end());
    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());
    show(ev);
    vector<int> path;
    ll ans = 1e18;
    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);
        }
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    for (int k : vert)
        dd[k] = 1e18;
    for (int i = 0; i < S; ++i) {
        q.emplace(0, X[i]);
        dd[X[i]] = 0;
    }

    show(vert);
    show(q);
    show(g0);
    show(dd);

    while (!q.empty()) {
        auto [D, v] = q.top();
        q.pop();
        if (dd[v] < D) continue;
        for (auto [k, w] : g0[v]) {
            if (dd[k] > dd[v] + w) {
                dd[k] = dd[v] + w;
                q.emplace(dd[k], k);
            }
        }
    }
    show(dd);

    for (int i = 0; i < T; ++i)
        ans = min(ans, dd[Y[i]]);

    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) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:163:5: note: in expansion of macro 'show'
  163 |     show(ev);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:188:5: note: in expansion of macro 'show'
  188 |     show(vert);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:189:5: note: in expansion of macro 'show'
  189 |     show(q);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:190:5: note: in expansion of macro 'show'
  190 |     show(g0);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:191:5: note: in expansion of macro 'show'
  191 |     show(dd);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:204:5: note: in expansion of macro 'show'
  204 |     show(dd);
      |     ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 696 KB Output is correct
2 Correct 1569 ms 9704 KB Output is correct
3 Correct 1636 ms 9512 KB Output is correct
4 Correct 1519 ms 9892 KB Output is correct
5 Correct 1365 ms 9932 KB Output is correct
6 Correct 1195 ms 9664 KB Output is correct
7 Correct 1639 ms 9716 KB Output is correct
8 Correct 1573 ms 9844 KB Output is correct
9 Correct 1362 ms 10036 KB Output is correct
10 Correct 1202 ms 9660 KB Output is correct
11 Correct 1641 ms 9808 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 2571 ms 155460 KB Output is correct
3 Correct 2757 ms 158652 KB Output is correct
4 Correct 2020 ms 156168 KB Output is correct
5 Correct 2432 ms 185900 KB Output is correct
6 Correct 2984 ms 159000 KB Output is correct
7 Correct 2759 ms 37960 KB Output is correct
8 Correct 1706 ms 37732 KB Output is correct
9 Correct 1806 ms 41588 KB Output is correct
10 Correct 2609 ms 38128 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 696 KB Output is correct
2 Correct 1569 ms 9704 KB Output is correct
3 Correct 1636 ms 9512 KB Output is correct
4 Correct 1519 ms 9892 KB Output is correct
5 Correct 1365 ms 9932 KB Output is correct
6 Correct 1195 ms 9664 KB Output is correct
7 Correct 1639 ms 9716 KB Output is correct
8 Correct 1573 ms 9844 KB Output is correct
9 Correct 1362 ms 10036 KB Output is correct
10 Correct 1202 ms 9660 KB Output is correct
11 Correct 1641 ms 9808 KB Output is correct
12 Correct 4 ms 460 KB Output is correct
13 Correct 2571 ms 155460 KB Output is correct
14 Correct 2757 ms 158652 KB Output is correct
15 Correct 2020 ms 156168 KB Output is correct
16 Correct 2432 ms 185900 KB Output is correct
17 Correct 2984 ms 159000 KB Output is correct
18 Correct 2759 ms 37960 KB Output is correct
19 Correct 1706 ms 37732 KB Output is correct
20 Correct 1806 ms 41588 KB Output is correct
21 Correct 2609 ms 38128 KB Output is correct
22 Correct 5398 ms 158144 KB Output is correct
23 Correct 4583 ms 159088 KB Output is correct
24 Correct 5642 ms 160956 KB Output is correct
25 Correct 5409 ms 162608 KB Output is correct
26 Correct 5193 ms 161584 KB Output is correct
27 Correct 4314 ms 182320 KB Output is correct
28 Correct 3392 ms 159948 KB Output is correct
29 Correct 4947 ms 161112 KB Output is correct
30 Correct 4981 ms 160544 KB Output is correct
31 Correct 5032 ms 161220 KB Output is correct
32 Correct 2384 ms 45816 KB Output is correct
33 Correct 2069 ms 43256 KB Output is correct
34 Correct 2942 ms 36664 KB Output is correct
35 Correct 2854 ms 36664 KB Output is correct
36 Correct 3190 ms 37396 KB Output is correct
37 Correct 3133 ms 37412 KB Output is correct