Submission #565587

#	Time	Username	Problem	Language	Result	Execution time	Memory
565587		shrimb	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4051 ms	33732 KiB

plan

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 100001;

vector<pair<int,int>> adj[maxn];
int mn[maxn], dist[maxn]; // closest npp

signed main () {
    cin.tie(0)->sync_with_stdio(0);

    int n, m, k, q;
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    cin >> k;
    int npp[k];
    for (int i = 0 ; i < k ; i++) cin >> npp[i];

    // multisource dijkstra
    priority_queue<pair<int,int>> pq; // {-distance, index}

    for (int& i : mn) i = INT_MAX;

    for (int i = 0 ; i < k ; i++) {
        mn[npp[i]] = 0;
        pq.push({0, npp[i]});
    }

    while (pq.size()) {
        auto [d, i] = pq.top();
        d = -d;
        pq.pop();
        if (mn[i] < d) continue;
        for (auto [j, w] : adj[i]) {
            if (d + w < mn[j]) {
                mn[j] = d + w;
                pq.push({-mn[j], j});
            }
        }
    }

    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        bool flag = 0;
        for (auto [j, w] : adj[s]) {
            if (j == t) {
                flag = 1;
                cout << min(mn[s], mn[t]) << endl;
                break;
            }
        }
        if (flag) continue;
        for (int i = 1 ; i <= n ; i++) dist[i] = -INT_MAX;
        pq.push({mn[s], s});
        dist[s] = mn[s];
        while (pq.size()) {
            auto [d, i] = pq.top();
            pq.pop();
            if (dist[i] > d) continue;
            for (auto [j, w] : adj[i]) {
                w = min(mn[j], d);
                if (w > dist[j]) {
                    dist[j] = w;
                    pq.push({w, j});
                }
            }
        }
        cout << dist[t] << endl;
    }
}

Compilation message (stderr)

plan.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

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