Submission #880297

#	Time	Username	Problem	Language	Result	Execution time	Memory
880297		dimashhh	Evacuation plan (IZhO18_plan)	C++17	100 / 100	610 ms	48816 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 12;
#define int long long
set<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] = 1e18;
    }
    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;
void merge(int v,int u){
    v = get(v);
    u = get(u);
    if(v == u) return;
    p[u] = v;
    if(qr[v].size() < qr[u].size()){
        qr[v].swap(qr[u]);
    }
    for(auto i:qr[u]){
        if(qr[v].find(i) == qr[v].end()){
            qr[v].insert(i);
        }else{
            res[i] = cur;
            qr[v].erase(i);
        }
    }
    qr[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(i);
        qr[t].insert(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;
    }
    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';
    }
}
main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    test();
}

Compilation message (stderr)

plan.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main(){
      | ^~~~

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