Submission #1266698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266698		rayan_bd	Evacuation plan (IZhO18_plan)	C++20	19 / 100	295 ms	27116 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 2e5 + 100;
const int INF = 1e9;
int par[mxN], sz[mxN], dist[mxN];
vector<pair<int, int>> adj[mxN];
struct dsu{
    void init(int n){
        for(int i = 1; i <= n; ++i){
            par[i] = i, sz[i] = 1;
        }
    }
    int find_par(int u){
        if(par[u] == u) return u;
        return par[u] = find_par(par[u]);
    }
    void unite(int u, int v){
        u = find_par(u), v = find_par(v);
        if(u == v) return;
        if(sz[u] > sz[v]){
            sz[u] += sz[v];
            par[v] = u;
        }else{
            sz[v] += sz[u];
            par[u] = v;
        }
    }
    bool connected(int u, int v){
        return find_par(u) == find_par(v);
    }
}ds;
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, q, u, v, w, k;
    cin >> n >> m;
    vector<pair<int, int>> edge;
    for(int i = 1; i <= n; ++i) dist[i] = INF;
    for(int i = 1; i <= m; ++i){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edge.push_back({u, v});
    }
    cin >> k;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for(int i = 1; i <= k; ++i){
        cin >> u;
        dist[u] = 0;
        pq.push({0, u});
    }
    while(pq.size()){
        auto tp = pq.top();
        pq.pop();
        if(tp.first > dist[tp.second]) continue;
        for(auto it : adj[tp.second]){
            if(dist[it.first] > tp.first + it.second){
                dist[it.first] = tp.first + it.second;
                pq.push({dist[it.first], it.first});
            }
        }
    }
    cin >> q;
    assert(q == 1);
    int u1 = -1, v1 = -1;
    for(int i = 0; i < q; ++i){
        cin >> u1 >> v1;
    }
    sort(all(edge), [&](pair<int, int> &p1, pair<int, int> &p2){
        return min(dist[p1.first], dist[p1.second]) > min(dist[p2.first], dist[p2.second]);
    });
    ds.init(n + 1);
    int ans = -1;
    for(int i = 0; i < edge.size(); ++i){
        ds.unite(edge[i].first, edge[i].second);
        if(ds.connected(u1, v1)){
            ans = min(dist[edge[i].first], dist[edge[i].second]);
            break;
        }
    }
    cout << ans << "\n";
    return 0;
}

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