Submission #880258

#	Time	Username	Problem	Language	Result	Execution time	Memory
880258		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	4043 ms	25872 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 12;
set<int> st[N];
set<pair<int,int>> qr[N];
int n,m,d[N],p[N],res[N];
vector<pair<int,int>> g[N];
void dijkstra(){
    int k;
    cin >> k;
    for(int i = 1;i <= n;i++){
        d[i] = 1e9;
    }
    set<pair<int,int>> st;
    for(int i = 1;i <= k;i++){
        int x;
        cin >> x;
        d[x] = 0;
        st.insert({0,x});
    }
    while(!st.empty()){
        int v = (*st.begin()).second;
        st.erase({d[v],v});
        for(auto [to,w]:g[v]){
            if(d[to] > d[v] + w){
                st.erase({d[to],to});
                d[to] = d[v] + w;
                st.insert({d[to],to});
            }
        }
    }
}
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
int cur = 0;
mt19937 rng;
void merge(int v,int u){
    v = get(v);
    u = get(u);
    if(v == u) return;
    p[u] = v;
    if(rng() & 1){
        qr[v].swap(qr[u]);
        st[v].swap(st[u]);
    }
    for(auto [x,y]:qr[u]){
        if(st[v].find(x) != st[v].end()){
            res[y] = cur;
        }else{
            qr[v].insert({x,y});
        }
    }
    for(auto i:st[u]){
        while(!qr[v].empty()){
            auto [x,y] = *qr[v].lower_bound(make_pair(i,0));
            if(x != i) break;
            res[y] = cur;
            qr[v].erase({x,y});
        }
        st[v].insert(i);
    }
    qr[u].clear();
    st[u].clear();
}
void test(){
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
    }
    dijkstra();
    int q;
    cin >> q;
    for(int i = 1;i <= q;i++){
        int s,t;
        cin >> s >> t;
        qr[s].insert({t,i});
        qr[t].insert({s,i});
    }
    vector<int> b(n);
    iota(b.begin(),b.end(),1);
    sort(b.begin(),b.end(),[&](int x,int y){
        return d[x] > d[y];
    });
    for(int i = 1;i <= n;i++){
        p[i] = i;
        st[i].insert(i);
    }
    for(auto i:b){
        cur = d[i];
        for(auto [to,w]:g[i]){
            if(d[to] > d[i]){
                merge(i,to);
            }
        }
    }
    for(int i = 1;i <= q;i++){
        cout << res[i] << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    test();
}

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