Submission #1194702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194702		Hamed_Ghaffari	Evacuation plan (IZhO18_plan)	C++20	100 / 100	326 ms	43592 KiB

plan

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

using pii = pair<int, int>;

#define X first
#define Y second

const int MXN = 1e5+5;
const int LOG = 17;
const int inf = 1e9;

int n, m, dis[MXN];
vector<pii> g[MXN], G[MXN];

int dsu[MXN], sz[MXN];

int find(int v) { return v==dsu[v] ? v : dsu[v] = find(dsu[v]); }
inline bool merge(int u, int v) {
    if((u=find(u))==(v=find(v))) return 0;
    if(sz[u]<sz[v]) swap(u, v);
    sz[dsu[v]=u] += sz[v];
    return 1;
}

int par[MXN][LOG], mn[MXN][LOG], h[MXN];

void dfs(int v) {
    for(int i=1; i<LOG; i++) {
        par[v][i] = par[par[v][i-1]][i-1];
        mn[v][i] = min(mn[v][i-1], mn[par[v][i-1]][i-1]);
    }
    for(auto [u, w] : G[v])
        if(u!=par[v][0]) {
            par[u][0] = v;
            mn[u][0] = w;
            h[u] = h[v]+1;
            dfs(u);
        }
}

inline int jump(int v, int d) {
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            v = par[v][i];
    return v;
}

inline int LCA(int u, int v) {
    if(h[u]<h[v]) swap(u, v);
    u = jump(u, h[u]-h[v]);
    if(u==v) return u;
    for(int i=LOG-1; i>=0; i--)
        if(par[v][i]!=par[u][i])
            v = par[v][i], u = par[u][i];
    return par[v][0];
}

inline int get(int v, int d) {
    int res = 1e9;
    for(int i=0; i<LOG; i++)
        if(d>>i&1)
            res = min(res, mn[v][i]),
            v = par[v][i];
    return res;
}

inline int get_path(int u, int v) {
    int lca = LCA(u, v);
    int res = 1e9;
    res = min(res, get(u, h[u]-h[lca]));
    res = min(res, get(v, h[v]-h[lca]));
    return res;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0, u,v,w; i<m; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int k;
    cin >> k;
    fill(dis+1, dis+n+1, inf);
    priority_queue<pii> pq;
    for(int i=0,v; i<k; i++) {
        cin >> v;
        dis[v] = 0;
        pq.push({0, v});
    }
    while(!pq.empty()) {
        int d = -pq.top().X, v = pq.top().Y;
        pq.pop();
        if(d!=dis[v]) continue;
        for(auto [u, w] : g[v])
            if(dis[u]>dis[v]+w)
                pq.push({-(dis[u]=dis[v]+w), u});
    }

    vector<pair<int, pii>> E;
    for(int v=1; v<=n; v++)
        for(auto [u, w] : g[v])
            if(u>v)
                E.push_back({min(dis[v], dis[u]), {v, u}});
    sort(E.begin(), E.end(), greater<>());
    iota(dsu+1, dsu+n+1, 1);
    fill(sz+1, sz+n+1, 1);
    for(auto [w, e] : E)
        if(merge(e.X, e.Y))
            G[e.X].push_back({e.Y, w}),
            G[e.Y].push_back({e.X, w});
    dfs(1);
    int q;
    cin >> q;
    while(q--) {
        int s, t;
        cin >> s >> t;
        cout << get_path(s, t) << '\n';
    }
    return 0;
}

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