Submission #1128654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128654		Skymagic	Evacuation plan (IZhO18_plan)	C++17	100 / 100	411 ms	40532 KiB

plan

#pragma GCC optimize("Ofast","unroll-loops")
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
*/
using namespace std;
#define ll long long
#define lgm cin.tie(0)->sync_with_stdio(0);
#define be(x) x.begin(),x.end()
#define v vector
#define f first
#define s second
#define pii pair<int, int>
#define tiii tuple<int,int,int>
#define pll pair<ll,ll>
#define sz(x) x.size()
#define eb emplace_back
#define pb push_back
const int mod = 1e9+7,maxn=100005;
int logn=20;
int n;
v<pii> ed[maxn];
int dist[maxn],dep[maxn];
int p[maxn][17],dp[maxn][17];
int pa[maxn];
v<tiii> temp;
priority_queue<pii, v<pii>, greater<pii>> pq;
int fp(int x) {
    if (pa[x] != x) return pa[x]=fp(pa[x]);
    return x;
}
void dfs(int u,int pa) {
    for (auto &[i,d]:ed[u]) {
        if (i == pa) continue;
        dep[i]=dep[u]+1;
        p[i][0]=u;
        dp[i][0]=dist[u];
        dfs(i,u);
    }
}
signed main() {
    lgm;
    int m;
    cin >> n >> m;
    for (int i=1;i<=n;++i) {
        pa[i]=i;
        dist[i]=1e9;
        for (int j=0;j<=16;j++) {
            dp[i][j]=1e9;
        }
    }
    int x,y,d;
    for (int i=0;i<m;++i) {
        cin >> x >> y >> d;
        ed[x].eb(y,d);
        ed[y].eb(x,d);
        temp.eb(0,x,y);
    }
    int q;
    cin >> q;
    while (q--) {
        cin >> x;
        dist[x]=0;
        pq.push({0,x});
    }
    while (!pq.empty()) {
        auto [d,x] = pq.top();
        pq.pop();
        if (d>dist[x]) continue;
        for (auto &[p,dd]:ed[x]) {
            if (dist[p] > d+dd) {
                dist[p]=d+dd;
                pq.push({dist[p],p});
            }
        }
    }
    for (auto &[d,i,j]:temp) {
        d=min(dist[i],dist[j]);
    }
    sort(be(temp),greater<tiii>());
    dp[1][0]=dist[1];
    for (int i=1;i<=n;++i) {
        ed[i]=v<pii>();
    }
    for (auto &[d,i,j]:temp) {
        int x=fp(i),y=fp(j);
        if (x==y) continue;
        ed[i].eb(j,dist[i]);
        ed[j].eb(i,dist[j]);
        pa[x]=y;
    }
    dfs(1,-1);
    for (int j=1;j<=16;++j) {
        for (int i=1;i<=n;++i) {
            p[i][j]=p[p[i][j-1]][j-1];
            dp[i][j]=min(dp[i][j-1],dp[p[i][j-1]][j-1]);
        }
    }
    cin >> q;
    int dis,ans;
    while (q--) {
        int x,y;
        cin >> x >> y;
        if (dep[x]<dep[y]) {
            swap(x,y);
        }
        dis=dep[x]-dep[y];
        ans=min(dist[x],dist[y]);
        for (int i=0;i<=16;++i) {
            if (dis & (1<<i)) {
                ans=min(ans,dp[x][i]);
                x=p[x][i];
            }
        }
        if (x == y) {
            cout << ans << '\n';
            continue;
        }
        for (int i=16;i>=0;--i) {
            if (p[x][i] != p[y][i]) {
                ans=min(ans,min(dp[x][i],dp[y][i]));
                x=p[x][i];
                y=p[y][i];
            }
        }
        ans=min(ans,min(dp[x][0],dp[y][0]));
        cout << ans << '\n';
    }
    return 0;
}

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