Submission #642171

#	Time	Username	Problem	Language	Result	Execution time	Memory
642171		joshjms	Evacuation plan (IZhO18_plan)	C++14	100 / 100	450 ms	35968 KiB

plan

#include <bits/stdc++.h>
using namespace std;

#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n"

const int mod = 998244353;
const ld E = 1e-4;

int n, m, k, q, ki[100005], a[100005], b[100005], ans[100005];
vector <pair<int,int>> g[100005];

int md[100005];
pair <int,int> c[100005];

void dijkstra() {
    for(int i = 1; i <= n; i++)
        md[i] = 1e9;
    priority_queue <pair<int,int>> pq;
    for(int i = 1; i <= k; i++) {
        pq.push({0, ki[i]});
        md[ki[i]] = 0;
    }
    while(!pq.empty()) {
        int cost = -pq.top().fi;
        int pos = pq.top().se;
        pq.pop();
        if(cost > md[pos]) continue;
        for(auto i : g[pos]) {
            if(md[i.fi] > cost + i.se) {
                md[i.fi] = cost + i.se;
                pq.push({-md[i.fi], i.fi});
            }
        }
    }
}

int par[100005];
vector <pair<int,int>> sack[100005];
bool unlock[100005];

int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}

int merge(int u, int v, int w) {
    u = find(u);
    v = find(v);
    if(u == v) return 0;
    if(sack[u].size() < sack[v].size()) {
        par[u] = v;
        for(auto i : sack[u]) {
            if(find(i.fi) == v)
                ans[i.se] = max(ans[i.se], w);
            else sack[v].pb(i);
        }
    }
    else {
        par[v] = u;
        for(auto i : sack[v]) {
            if(find(i.fi) == u)
                ans[i.se] = max(ans[i.se], w);
            else sack[u].pb(i);
        }
    }
    return 1;
}

void solve () {
    cin >> n >> m;
    for(int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> ki[i];
    }
    dijkstra();
    // for(int i = 1; i <= n; i++)
    //     cout << md[i] << " ";
    // cout << "\n";
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> a[i] >> b[i];
        sack[a[i]].pb({b[i], i});
        sack[b[i]].pb({a[i], i});
    }
    for(int i = 1; i <= n; i++)
        par[i] = i;
    for(int i = 1; i <= n; i++) 
        c[i] = {md[i], i};
    sort(c + 1, c + n + 1, greater<pair<int,int>>());
    for(int i = 1; i <= q; i++)
        ans[i] = -1;
    for(int i = 1; i <= n; i++) {
        int u = c[i].se;
        unlock[u] = true;
        for(auto v : g[u]) {
            if(unlock[v.fi]) {
                merge(u, v.fi, c[i].fi);
            }
        }
    }
    for(int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve ();
}

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