Submission #1165625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165625		altern23	Evacuation plan (IZhO18_plan)	C++20	23 / 100	471 ms	120376 KiB

plan

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;

vector<ll> Q[N + 5];
ll ada[N + 5], lst[N + 5];
map<pii, ll> ans;

struct DSU{
    ll n;
    vector<ll> par;
    DSU(ll _n){
        n = _n;
        par = vector<ll>(n + 5);
        for(int i = 1; i <= n; i++) par[i] = i;
    }
    ll find(ll idx){
        if(par[idx] == idx) return idx;
        return par[idx] = find(par[idx]);
    }
    bool join(ll a, ll b){
        a = find(a), b = find(b);
        if(a == b) return false;
        par[b] = a;
        return true;
    }
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, m; cin >> n >> m;
        vector<pii> adj[n + 5];
        for(int i = 1; i <= m; i++){
            ll a, b, w; cin >> a >> b >> w;
            adj[a].push_back({b, w});
            adj[b].push_back({a, w});
        }

        ll k; cin >> k;
        vector<ll> g(k + 5), dp(n + 5, INF);
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for(int i = 1; i <= k; i++){
            cin >> g[i];
            dp[g[i]] = 0;
            pq.push({dp[g[i]], g[i]});
        }
        
        for(;!pq.empty();){
            auto [dist, node] = pq.top(); pq.pop();
            if(dp[node] < dist) continue;
            for(auto [i, j] : adj[node]){
                if(dp[i] > dist + j){
                    dp[i] = dist + j;
                    pq.push({dp[i], i});
                }
            }
        }

        DSU dsu(n);
        vector<pair<ll, pii>> edges;
        for(int i = 1; i <= n; i++){
            for(auto [u, _] : adj[i]){
                edges.push_back({min(dp[i], dp[u]), {i, u}});
            }
        }

        sort(edges.begin(), edges.end(), greater<pair<ll, pii>>());
        vector<pii> adj2[n + 5];
        for(auto [dist, node] : edges){
            if(dsu.join(node.fi, node.sec)){
                adj2[node.fi].push_back({node.sec, dist});
                adj2[node.sec].push_back({node.fi, dist});
            }
        }

        queue<ll> que;
        que.push(1);
        vector<ll> dist(n + 5, INF);
        dist[1] = 0;
        vector<pii> par(n + 5);
        par[1] = {0, INF};
        for(;!que.empty();){
            auto x = que.front(); que.pop();
            for(auto [i, j] : adj2[x]){
                if(dist[i] > dist[x] + 1){
                    dist[i] = dist[x] + 1;
                    par[i] = {x, j};
                    que.push(i);
                }
            }
        }
        
        vector<vector<ll>> up(n + 5, vector<ll>(30)), mn(n + 5, vector<ll>(30));
        for(int LOG = 0; LOG < 30; LOG++){
            for(int i = 1; i <= n; i++){
                if(LOG == 0){
                    up[i][LOG] = par[i].fi;
                    mn[i][LOG] = par[i].sec;
                }
                else{
                    up[i][LOG] = up[up[i][LOG - 1]][LOG - 1];
                    mn[i][LOG] = min(mn[i][LOG - 1], mn[up[i][LOG - 1]][LOG - 1]);
                }
            }
        }

        auto query = [&](ll s, ll t){
            if(dist[s] < dist[t]) swap(s, t);
            ll res = dist[s] - dist[t];
            ll ans = INF;
            for(int LOG = 0; LOG < 30; LOG++){
                if(res & (1LL << LOG)){
                    ans = min(ans, mn[s][LOG]);
                    s = up[s][LOG];
                }
            }
            for(int LOG = 29; LOG >= 0; LOG--){
                if(up[s][LOG] != up[t][LOG]){
                    ans = min({ans, mn[s][LOG], mn[t][LOG]});
                    s = up[s][LOG], t = up[t][LOG];
                }
            }
            ans = min({ans, dp[s], dp[t]});
            return ans;
        };

        ll q; cin >> q;
        for(int i = 1; i <= q; i++){
            ll s, t; cin >> s >> t;
            cout << query(s, t) << "\n";
        }
    }   
}

/*

*/ 

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