Submission #642906

#	Time	Username	Problem	Language	Result	Execution time	Memory
642906		KiriLL1ca	Evacuation plan (IZhO18_plan)	C++14	100 / 100	533 ms	45232 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)
#define sz(x) (int)((x).size())
#define pb push_back
#define endl '\n'
#define mp make_pair
#define vec vector

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

inline void solve () {
        int n, m; cin >> n >> m;
        vector <vector <pii>> g (n);
        vector <array <int, 3>> edge (m);
        for (int i = 0; i < m; ++i) {
                int u, v, w; cin >> u >> v >> w; --u, --v;
                g[u].pb({v, w}); g[v].pb({u, w}); edge[i] = {0, u, v};
        }
        int k; cin >> k;
        vector <int> hui (k);
        for (auto &i : hui) cin >> i, --i;

        priority_queue <pii, vector <pii>, greater <pii>> pq;
        vector <int> dist (n, 1e9);
        for (auto i : hui) {
                dist[i] = 0; pq.push({0, i});
        }

        while (sz(pq)) {
                auto [d, v] = pq.top(); pq.pop();
                if (dist[v] > d) continue;
                for (auto [u, w] : g[v]) {
                        if (dist[u] > d + w) {
                                dist[u] = d + w;
                                pq.push({dist[u], u});
                        }
                }
        }

        for (auto &[w, u, v] : edge) w = min(dist[u], dist[v]);
        sort(rall(edge));

        int q; cin >> q;
        vector <vector <pii>> qry (n);
        vector <int> ans (q);
        for (int i = 0; i < q; ++i) {
                int s, t; cin >> s >> t; --s, --t;
                qry[s].pb({t, i}); qry[t].pb({s, i});
        }

        vector <int> p (n); iota(all(p), 0);
        vector <vector <int>> sub (n); for (int i = 0; i < n; ++i) sub[i].pb(i);

        function <int(int)> par = [&] (int x) { return (p[x] != x ? p[x] = par(p[x]) : x); };
        auto unite = [&] (int x, int y, int cost) {
                x = par(x); y = par(y);
                if (x == y) return;
                if (sz(sub[x]) < sz(sub[y])) swap(x, y);
                for (auto u : sub[y]) {
                        for (auto [v, id] : qry[u]) {
                                if (par(v) == x) ans[id] = cost;
                        }
                        sub[x].pb(u);
                }
                p[y] = x; sub[y].clear();
        };

        for (auto [w, u, v] : edge) unite(u, v, w);
        for (auto i : ans) cout << i << endl;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:47:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |                 auto [d, v] = pq.top(); pq.pop();
      |                      ^
plan.cpp:49:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |                 for (auto [u, w] : g[v]) {
      |                           ^
plan.cpp:57:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for (auto &[w, u, v] : edge) w = min(dist[u], dist[v]);
      |                    ^
plan.cpp: In lambda function:
plan.cpp:77:35: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |                         for (auto [v, id] : qry[u]) {
      |                                   ^
plan.cpp: In function 'void solve()':
plan.cpp:85:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         for (auto [w, u, v] : edge) unite(u, v, w);
      |                   ^

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