Submission #642123

#	Time	Username	Problem	Language	Result	Execution time	Memory
642123		joshjms	Evacuation plan (IZhO18_plan)	C++17	41 / 100	4035 ms	57428 KiB

plan

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

#define int long long
#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] = 1e18;
    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];
set <int> st[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;
    vector <int> tmp;
    for(auto i : st[u]) if(st[v].count(i)) tmp.pb(i);
    for(auto i : tmp) {
        ans[i] = w;
        st[u].erase(i);
        st[v].erase(i);
    }
    if(st[u].size() < st[v].size()) {
        par[u] = v;
        for(auto i : st[u]) st[v].insert(i);
    }
    else {
        par[v] = u;
        for(auto i : st[v]) st[u].insert(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];
        st[a[i]].insert(i);
        st[b[i]].insert(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 <= 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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46