Submission #1089438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089438		kaopj	Evacuation plan (IZhO18_plan)	C++17	22 / 100	4094 ms	36344 KiB

plan

#include <iostream>
#include <vector>
#include <map>
#include <deque>
#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()
const int mod = 1e9+7,maxn=100005;
int logn=20;
int n;
v<pii> ed[maxn];
v<int> dist(maxn,1e9),dep(maxn,0);
v<v<int>> p(maxn,v<int>(20)),dp(maxn,v<int>(20,1e9));
int pa[maxn];
v<tiii> temp;
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]=min(dist[i],dist[u]);
        dfs(i,u);
    }
}
signed main() {
    lgm;
    int m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) {
        pa[i]=i;
    }
    int x,y,d;
    for (int i=0;i<m;i++) {
        cin >> x >> y >> d;
        ed[x].push_back({y,d});
        ed[y].push_back({x,d});
    }
    int q;
    cin >> q;
    priority_queue<pii> pq;
    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});
            }
        }
    }
    dp[1][0]=dist[1];
    for (int i=1;i<=n;i++) {
        for (auto [u,j]:ed[i]) {
            temp.push_back({min(dist[i],dist[u]),i,u});
        }
        ed[i].clear();
    }
    sort(be(temp),greater<tiii>());
    for (auto [d,i,j]:temp) {
        int x=fp(i),y=fp(j);
        if (x==y) continue;
        ed[i].push_back({j,0});
        ed[j].push_back({i,0});
        pa[x]=y;
    }
    dfs(1,-1);
    for (int j=1;j<=17;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<=17;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=17;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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46