Submission #1199259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199259		prikpao	Evacuation plan (IZhO18_plan)	C++20	41 / 100	4090 ms	35132 KiB

plan

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define st first
#define nd second
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define t3 tuple<int, int, int>
#define t4 tuple<int, int, int, int>
#define chmn(a, b) a=min(a, b)
#define chmx(a, b) a=max(a, b)
#define For(i, a, b) for(int i=(int)a; i<=(int)b; i++)
#define Forx(i, a, b, x) for(int i=(int)a; i<=(int)b; i+=(int)x)
#define F0r(i, n) for(int i=0; i<(int)n; i++)
#define Rof(i, a, b) for(int i=(int)a; i>=(int)b; i--)
#define R0f(i, n) for(int i=(int)(n-1); i>=(int)0; i--)
#define rep(n) F0r(_, (int)n)
#define all(v) (v).begin(), (v).end()
const int N = 1e5+5;
using ll = long long;
using namespace std;
#define int ll

struct A{
    int a, mn;
    bool operator<(const A& o)const{
        return mn<o.mn;
    }
};
struct B{
    int a, w;
    bool operator<(const B& o)const{
        return w>o.w;
    }
};

int dis[N], mp[N];
vector<B> g[N];

void solve(){
    int n, m, k, q, a, b, w, s, t;
    cin >> n >> m;
    rep(m){
        cin >> a >> b >> w;
        g[a].pb({b, w});
        g[b].pb({a, w});
    }
    cin >> k;
    priority_queue<B> pq;
    fill(dis+1, dis+n+1, 1e18);
    rep(k){
        cin >> a;
        pq.push({a, 0});
        dis[a]=0;
    }
    while(!pq.empty()){
        auto [a,w]=pq.top();
        pq.pop();

        if(w>dis[a])continue;
        for(auto i:g[a]){
            if(w+i.w<dis[i.a]){
                dis[i.a]=w+i.w;
                pq.push({i.a, w+i.w});
            }
        }
    }
    //For(i, 1, n)cout << dis[i] << ' ';cout << '\n';
    cin >> q;
    priority_queue<A> pq2;
    unordered_map<int, int> mp;
    rep(q){
        mp.clear();
        while(!pq2.empty())pq2.pop();
        cin >> s >> t;
        mp[s]=dis[s];
        pq2.push({s, dis[s]});
        while(!pq2.empty()){
            auto [a,mn]=pq2.top();
            pq2.pop();

            if(mp.count(a) && mn<mp[a])continue;
            //cout << a << ' ' << mn << '\n';
            if(a==t){
                cout << mn << '\n';
                break;
            }
            for(auto i:g[a]){
                int newm=min(mn, dis[i.a]);
                if(!mp.count(i.a) || newm>mp[i.a]){
                    mp[i.a]=newm;
                    pq2.push({i.a, newm});
                }
            }
        }
        //cout << "---------\n";
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    int Tcases=1;
    //cin >> Tcases;
    while(Tcases--)solve();
    return 0;
}

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