Submission #527137

#	Time	Username	Problem	Language	Result	Execution time	Memory
527137		jalsol	Evacuation plan (IZhO18_plan)	C++11	100 / 100	558 ms	54724 KiB

plan

// looking to shine brighter in this world...

#ifdef LOCAL
#include "local_header.h"
#include "debugger.h"
#else
#include <bits/stdc++.h>
#define debug(...)
#define DB(...)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

using namespace std;

static const bool __initialization = [] {
    cin.tie(nullptr)->sync_with_stdio(false);
#define TASK "NPP"
    if (fopen(TASK".inp", "r")) {
        (void)(!freopen(TASK".inp", "r", stdin));
        (void)(!freopen(TASK".out", "w", stdout)); }
    cout << setprecision(12) << fixed;
    return true;
}();

using ll = long long;
using ld = long double;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)
#define Fe(...) for (const auto& __VA_ARGS__)
#define Fa(...) for (auto __VA_ARGS__)

template <class C> inline int isz(const C& c) { return static_cast<int>(c.size()); }
template <class T> inline bool chmin(T& a, const T& b) { return (a > b) ? a = b, true : false; }
template <class T> inline bool chmax(T& a, const T& b) { return (a < b) ? a = b, true : false; }

constexpr ld eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxn = 1e5 + 5;
constexpr int logn = 20;

using P = pair<int, int>;

struct E {
    int u, v, c;

    bool operator<(const E& o) const {
        return c < o.c;
    }
};

struct Dsu {
    int par[maxn];

    Dsu() {
        memset(par, -1, sizeof(par));
    }

    int find(int x) {
        return (par[x] < 0) ? x : par[x] = find(par[x]);
    }

    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;

        if (par[v] < par[u]) swap(u, v);
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

int n, ne, nq;
vector<P> g[maxn];
int nk;
int src[maxn];

int d[maxn];
priority_queue<P, vector<P>, greater<P>> q;

vector<E> e;
Dsu dsu;

vector<P> tree[maxn];
int up[maxn][logn];
int dist[maxn][logn];
int dep[maxn];

void addEdge(int u, int v, int c) {
    tree[u].emplace_back(v, c);
    tree[v].emplace_back(u, c);
}

void Dfs(int u) {
    Fe ([v, c] : tree[u]) {
        if (v == up[u][0]) continue;

        up[v][0] = u;
        dist[v][0] = c;
        dep[v] = dep[u] + 1;
        Dfs(v);
    }
}

int getDist(int u, int v) {
    if (u == v) return 0;

    int ret = inf;

    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];

    Repd (i, logn) {
        if (diff >> i & 1) {
            chmin(ret, dist[u][i]);
            u = up[u][i];
        }
    }

    if (u == v) return ret;

    Repd (i, logn) {
        if (up[u][i] != up[v][i]) {
            chmin(ret, dist[u][i]);
            chmin(ret, dist[v][i]);
            u = up[u][i];
            v = up[v][i];
        }
    }

    return min({ret, dist[u][0], dist[v][0]});
}

signed main() {
    cin >> n >> ne;

    Rep (_, ne) {
        int u, v, c; cin >> u >> v >> c;
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }

    memset(d, 0x3f, sizeof(d));
    cin >> nk;

    For (i, 1, nk) {
        cin >> src[i];
        d[src[i]] = 0;
        q.emplace(0, src[i]);
    }

    sort(src + 1, src + nk + 1);

    while (isz(q)) {
        auto [du, u] = q.top(); q.pop();
        if (du != d[u]) continue;

        Fe ([v, c] : g[u]) {
            if (chmin(d[v], d[u] + c)) {
                q.emplace(d[v], v);
            }
        }
    }

    e.reserve(ne);

    For (u, 1, n) {
        if (binary_search(src + 1, src + nk + 1, u)) {
            continue;
        }

        Fe ([v, c] : g[u]) {
            if (u >= v) continue;

            if (!binary_search(src + 1, src + nk + 1, v)) {
                e.push_back({u, v, min(d[u], d[v])});
            }
        }
    }

    sort(rall(e));

    Fe ([u, v, c] : e) {
        if (dsu.merge(u, v)) {
            addEdge(u, v, c);
        }
    }

    int root = n + 1;

    For (i, 1, n) {
        if (dsu.merge(root, i)) {
            addEdge(root, i, 0);
        }
    }

    For (i, 1, nk) {
        if (dsu.merge(root, src[i])) {
            addEdge(root, src[i], 0);
        }
    }

    Dfs(root);

    For (j, 1, logn - 1) {
        For (i, 1, root) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            dist[i][j] = min(dist[i][j - 1], dist[up[i][j - 1]][j - 1]);
        }
    }

    cin >> nq;

    Rep (_, nq) {
        int u, v; cin >> u >> v;
        cout << getDist(u, v) << '\n';
    }
}

Compilation message (stderr)

plan.cpp: In function 'void Dfs(int)':
plan.cpp:108:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |     Fe ([v, c] : tree[u]) {
      |         ^
plan.cpp:38:34: note: in definition of macro 'Fe'
   38 | #define Fe(...) for (const auto& __VA_ARGS__)
      |                                  ^~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:168:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |         auto [du, u] = q.top(); q.pop();
      |              ^
plan.cpp:171:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  171 |         Fe ([v, c] : g[u]) {
      |             ^
plan.cpp:38:34: note: in definition of macro 'Fe'
   38 | #define Fe(...) for (const auto& __VA_ARGS__)
      |                                  ^~~~~~~~~~~
plan.cpp:185:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  185 |         Fe ([v, c] : g[u]) {
      |             ^
plan.cpp:38:34: note: in definition of macro 'Fe'
   38 | #define Fe(...) for (const auto& __VA_ARGS__)
      |                                  ^~~~~~~~~~~
plan.cpp:196:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  196 |     Fe ([u, v, c] : e) {
      |         ^
plan.cpp:38:34: note: in definition of macro 'Fe'
   38 | #define Fe(...) for (const auto& __VA_ARGS__)
      |                                  ^~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46