제출 #1266701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266701		rayan_bd	Evacuation plan (IZhO18_plan)	C++20	100 / 100	487 ms	57412 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

const int mxN = 5e5 + 100;
const int INF = 1e9;

int par[mxN], sz[mxN], dist[mxN], query[mxN][2], st[mxN], en[mxN], ans[mxN];
vector<pair<int, int>> adj[mxN];
vector<int> point[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;
    for(int i = 0; i < q; ++i){
        cin >> query[i][0] >> query[i][1];
        st[i] = 0, en[i] = m - 1;
        point[st[i] + (en[i] - st[i]) / 2].push_back(i);
    }
    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]);
    });
    for(int i = 0; i < 28; ++i){
        ds.init(n + 5);
        for(int j = 0; j < m; ++j){
            ds.unite(edge[j].first, edge[j].second);
            for(auto it : point[j]){
                if(ds.connected(query[it][0], query[it][1])){
                    ans[it] = j;
                    en[it] = j - 1;
                }else{
                    st[it] = j + 1;
                }
            }
            point[j].clear();
        }
        for(int i = 0; i < q; ++i){
            if(st[i] <= en[i]) point[st[i] + (en[i] - st[i]) / 2].push_back(i);
        }
    }
    for(int i = 0; i < q; ++i){
        cout << min(dist[edge[ans[i]].first], dist[edge[ans[i]].second]) << "\n";
    }
    return 0;
}

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