Submission #387836

#	Time	Username	Problem	Language	Result	Execution time	Memory
387836		maksim1744	Factories (JOI14_factories)	C++17	0 / 100	35 ms	836 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<vector<pair<int, ll>>> g0;
vector<ll> dd;

vector<int> tp;
void Init(int N, int A[], int B[], int D[]) {
    int n = N;
    tp.resize(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]);
        tp[X[i]] = 1;
    }
    for (int i = 0; i < T; ++i) {
        vert.pb(Y[i]);
        tp[Y[i]] = 2;
    }
    sort(vert.begin(), vert.end());
    vert.erase(unique(vert.begin(), vert.end()), vert.end());
    if (vert.size() != S + T) return 0;
    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]));
    }
    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 (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) {
      |                     ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:154:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  154 |     if (vert.size() != S + T) return 0;
      |         ~~~~~~~~~~~~^~~~~~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:166:5: note: in expansion of macro 'show'
  166 |     show(ev);
      |     ^~~~
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(vert);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:192:5: note: in expansion of macro 'show'
  192 |     show(q);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:193:5: note: in expansion of macro 'show'
  193 |     show(g0);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:194:5: note: in expansion of macro 'show'
  194 |     show(dd);
      |     ^~~~
factories.cpp:42:23: warning: statement has no effect [-Wunused-value]
   42 | #define show(...)     42
      |                       ^~
factories.cpp:207:5: note: in expansion of macro 'show'
  207 |     show(dd);
      |     ^~~~

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