Submission #1199234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199234		gugug	Evacuation plan (IZhO18_plan)	C++17	54 / 100	4091 ms	97964 KiB

plan

//#pragma GCC optimize("Ofast, unroll-loops")
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 1e5 + 5;
const ll inf = 1e18;

ll n, m;
priority_queue<pll, vector<pll>, greater<pll>> gpq;
priority_queue<pll> pq;
map<pll, bool> mp;
vector<pll> edge[maxn];
vector<ll> dist(maxn, inf);
bool visited[maxn];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        ll u, v, w; cin >> u >> v >> w;
        edge[u].emplace_back(v, w);
        edge[v].emplace_back(u, w);
        mp[{u, v}] = mp[{v, u}] = true;
    }

    ll npp_cnt;
    cin >> npp_cnt;
    for (int i = 0; i < npp_cnt; i++) {
        ll x; cin >> x;
        gpq.emplace(dist[x] = 0, x); 
    }  

    //dijkstra
    while (!gpq.empty()) {
        auto [curdist, u] = gpq.top(); gpq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (auto [v, todist] : edge[u]) {
            if (dist[v] > dist[u] + todist) {
                dist[v] = dist[u] + todist;
                gpq.emplace(dist[v], v);
            }
        }
    }

    ll q;
    cin >> q;

    while (q--) {
        ll s, t; cin >> s >> t;

        if (mp[{s, t}]) {
            cout << min(dist[s], dist[t]) << '\n';
            continue;
        }

        while (!pq.empty()) pq.pop();
        vector<ll> D(n + 5, -1);
        memset(visited, 0, sizeof(visited));
        D[s] = dist[s];
        pq.emplace(D[s], s);
        while (!pq.empty()) {
            auto [curmax, u] = pq.top(); pq.pop();
            if (visited[u]) continue;
            visited[u] = 1;
            D[u] = curmax;
            if (u == t) {
                break;
            }
            for (auto [v, tomax] : edge[u]) {
                ll smt = min(dist[v], curmax);
                if (D[v] < smt) {
                    D[v] = smt;
                    pq.emplace(smt, v);
                }
            }
        }
        cout << D[t] << '\n';
    }

    return 0;
}

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