Submission #565704

#	Time	Username	Problem	Language	Result	Execution time	Memory
565704		shrimb	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1983 ms	125328 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 = 200001;

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

int dsu[maxn];
vector<array<int, 5>> mids[maxn];
int ans[maxn];
bitset<maxn> inserted;

int Find (int x) {
    return dsu[x] == x ? x : dsu[x] = Find(dsu[x]);
}

void Union (int a, int b) {
    dsu[Find(a)] = Find(b);
}

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});
            }
        }
    }

    vector<pair<int,int>> opt = {{INT_MAX, n + 1}};
    for (int i = 1 ; i <= n ; i++) {
        opt.push_back({mn[i], i});
    }
    sort(opt.begin(), opt.end());
    reverse(opt.begin(), opt.end());

    // {query index, S, T, l, r}

    cin >> q;
    for (int i = 0 ; i < q ; i++) {
        int s, t;
        cin >> s >> t;
        int l = -1, r = n;
        mids[(l + r) / 2].push_back({i, s, t, l, r});
    }

    int it = 30;
    while (it--) {
        inserted = 0;
        for (int i = 1 ; i <= n ; i++) dsu[i] = i;
        for (int i = 0 ; i <= n ; i++) {
            inserted[opt[i].second] = 1;
            for (auto [j,w] : adj[opt[i].second]) if(inserted[j]) Union(j, opt[i].second);
            for (auto [idx, s, t, l, r] : mids[i]) {
                if (Find(s) == Find(t)) {
                    r = i;
                    ans[idx] = opt[r].first;
                } else {
                    l = i;
                    // cerr << s << " " << t << " " << opt[i].first << endl;
                }
                if (r - l > 1) {
                    int mid = (l + r) / 2;
                    mids[mid].push_back({idx, s, t, l, r});
                }
            }
            mids[i].clear();
        }
    }
    for (int i = 0 ; i < q ; i++) cout << ans[i] << 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: 46 / 46