Submission #1112590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112590		Icelast	Evacuation plan (IZhO18_plan)	C++17	100 / 100	888 ms	68796 KiB

plan

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct que{
    int u, v, id;
};
void dijkstra(vector<ll> &dist, int n, vector<vector<pair<ll, ll>>> &adj){
    vector<bool> vis(n+1, false);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    for(int i = 1; i <= n; i++){
        if(dist[i] == 0) pq.push({0, i});
    }
    while(!pq.empty()){
        ll d_u = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(vis[u]){
            continue;
        }
        vis[u] = true;
        for(auto it : adj[u]){
            int v = it.first;
            ll w = it.second;
            if(vis[v]) continue;
            if(dist[v] > d_u+w){
                dist[v] = d_u+w;
                pq.push({dist[v], v});
            }
        }
    }
}
struct DSU{
    int n;
    vector<int> pa, sz;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
        }
    };
    int find(int x){
        while(x != pa[x]){
            x = pa[x] = pa[pa[x]];
        }
        return x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x, y);
        pa[y] = x;
        sz[x] += sz[y];
        return true;
    }
    int size(int x){
        return sz[find(x)];
    }
};
void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(n+1);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<ll> dist(n+1, INF);
    int k;
    cin >> k;
    for(int i = 1; i <= k; i++){
        int v;
        cin >> v;
        dist[v] = 0;
    }
    int Q;
    cin >> Q;
    vector<que> q(Q+1);
    for(int i = 1; i <= Q; i++){
        cin >> q[i].u >> q[i].v;
        q[i].id = i;
    }
    dijkstra(dist, n, adj);
    dist[0] = INF;
    vector<int> idx(n+1);
    iota(idx.begin()+1, idx.end(), 1);

    sort(idx.begin()+1, idx.end(), [&](int a, int b){return dist[a] > dist[b];});
    vector<int> l(Q+1, 1), r(Q+1, n);
    vector<vector<que>> sweep(n+1);
    for(int it = 1; it <= 20; it++){
        DSU dsu(n);
        for(int i = 0; i <= n; i++) sweep[i].clear();
        for(int i = 1; i <= Q; i++){
            if(l[i] > r[i]) continue;
            int mid = (l[i]+r[i])/2;
            sweep[mid].push_back(q[i]);
        }
        for(int i = 1; i <= n; i++){
            int u = idx[i];
            for(auto it : adj[u]){
                int v = it.first;
                if(dist[v] >= dist[u]){
                    dsu.merge(u, v);
                }
            }
            for(auto it : sweep[i]){
                if(dsu.same(it.u, it.v)){
                    r[it.id] = i-1;
                }else{
                    l[it.id] = i+1;
                }
            }
        }
    }
    for(int i = 1; i <= Q; i++){
        cout << dist[idx[l[i]]] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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