Submission #637777

#	Time	Username	Problem	Language	Result	Execution time	Memory
637777		bonk	Evacuation plan (IZhO18_plan)	C++14	41 / 100	4062 ms	21216 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;
vector<pair<int, int>>adj[N];
bool vis[N];
int danger[N];
vector<int>tmp;

void init(){
    for(auto &x: tmp) vis[x] = 0;
    tmp.clear();
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(danger, 0x3f, sizeof(danger));
    int n, m; cin >> n >> m;
    while(m--){
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    int k; cin >> k;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
    for(int i = 0; i < k; i++){
        int x; cin >> x;
        danger[x] = 0;
        pq.emplace(0, x);
    }

    while(!pq.empty()){
        auto [d, u] = pq.top(); pq.pop();
        for(auto &[v, w]: adj[u]){
            if(danger[v] > d + w){
                danger[v] = d + w;
                pq.emplace(danger[v], v);
            }
        }
    }

    int q; cin >> q;

    while(q--){
        init();
        int a, b; cin >> a >> b;
        priority_queue<pair<int, int>>pq;
        pq.emplace(danger[a], a);
        int ans = min(danger[a], danger[b]);
        bool found = false;

        while(!pq.empty()){
            if(found) break;
            auto [d, u] = pq.top(); pq.pop();
            if(vis[u]) continue;
            vis[u] = true;
            tmp.push_back(u);

            for(auto &[v, w]: adj[u]){
                if(!vis[v]){
                    if(v == b){
                        ans = min(ans, d);
                        found = true;
                    }
                    pq.emplace(min(d, danger[v]), v);    
                }
            }
        }

        cout << ans << '\n';
    } 

    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:35:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |         auto [d, u] = pq.top(); pq.pop();
      |              ^
plan.cpp:36:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |         for(auto &[v, w]: adj[u]){
      |                   ^
plan.cpp:56:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |             auto [d, u] = pq.top(); pq.pop();
      |                  ^
plan.cpp:61:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |             for(auto &[v, w]: adj[u]){
      |                       ^

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