Submission #1209547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209547		asdfghqwert	Evacuation plan (IZhO18_plan)	C++20	100 / 100	1293 ms	55888 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef  long long ll;
const int maxn = 3e5 + 1 , delta = 66529;
#define int     long long int
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , m ; cin >> n >> m;
    vector<vector<pair<int , int>>> g(n + 1);
    for(int i = 1 ; i <= m ; i++){
        int u , v , w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int k; cin >> k;
    vector<int> k_nodes(k) ,  dis(n + 1, LLONG_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 0 ; i < k ; i++) {
        cin >> k_nodes[i];
        dis[k_nodes[i]] = 0;
        pq.push({0, k_nodes[i]});
    }
    while(!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if(d > dis[u]) continue;
        for(auto [v, w] : g[u]) {
            if(dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({dis[v], v});
            }
        }
    }
    vector<pair<int , int>> sorted_dis(n + 1);
    for(int i = 1 ; i <= n ; i++) sorted_dis[i] = {dis[i], i};
    sort(sorted_dis.begin() + 1, sorted_dis.end());
    int q; cin >> q;
    vector<pair<int , int>> queries(q) , ranges(q , {1 , n});
    for(int i = 0 ; i < q ; i++) {
        cin >> queries[i].first >> queries[i].second;
    }
    bool isfinished = false;
    vector<vector<int>> pos(n + 1);
    while(isfinished == false) {
        isfinished = true;
        // Clear pos for each iteration
        for(int i = 1; i <= n; i++) pos[i].clear();

        for(int i = 0 ; i < q ; i++) {
            if(ranges[i].first != ranges[i].second) {
                isfinished = false;
                int mid = (ranges[i].first + ranges[i].second + 1) / 2;
                pos[mid].push_back(i);
            }
        }
        //dsu
        vector<int> parent(n + 1);
        for(int i = 1 ; i <= n ; i++) {
            parent[i] = i;
        }
        function<int(int)> find = [&](int x) {
            if(parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        for(int i = n ; i >= 1 ; i--){
            int u = sorted_dis[i].second;
            for(auto [v, w] : g[u]) {
                if(dis[v] >= dis[u]) {
                    int pu = find(u);
                    int pv = find(v);
                    if(pu != pv) {
                        parent[pu] = pv;
                    }
                }
            }
            for(auto idx : pos[i]) {
                auto [l, r] = ranges[idx];
                if(l == r) continue;
                int mid = (l + r + 1) / 2;
                auto [x, y] = queries[idx];
                if(find(x) == find(y)) {
                    ranges[idx].first = mid;
                } else {
                    ranges[idx].second = mid - 1;
                }
            }
        }
    }
    for(int i = 0 ; i < q ; i++) {
        cout << sorted_dis[ranges[i].first].first << "\n";
    }
}

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