Submission #1267997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267997		wedonttalkanymore	Evacuation plan (IZhO18_plan)	C++20	100 / 100	474 ms	80500 KiB

plan

#include <bits/stdc++.h>
/*
    Strat code: 
    - Thinking about how to solve the full problems: 15 min
    - Thinking about subtasks + code: 30 min
    - Stress: 10 - 15 min
    => Total need 2h15m
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 5e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, m;
struct item {
    int u, v, w;
} a[N];
vector <pii> adj[N], adj1[N];
int k;
int p[N], length[N];
int q;

void dijk() {
    for (int i = 1; i <= n; i++) {
        length[i] = inf;
    }
    priority_queue <pii, vector <pii>, greater <pii> > pq;
    for (int i = 1; i <= k; i++) {
        length[p[i]] = 0;
        pq.push({0, p[i]});
    }
    while(pq.size()) {
        auto [c, u] = pq.top();
        pq.pop();
        if (c > length[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (length[v] > length[u] + w) {
                length[v] = length[u] + w;
                pq.push({length[v], v});
            }
        }
    }
}

bool cmp(item a, item b) {
    int x = min(length[a.u], length[a.v]);
    int y = min(length[b.u], length[b.v]);
    return x > y;
}

struct krushkal {
    int par[N], sz[N];
    void makeset() {
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    void join(int u, int v) {
        u = find(u), v = find(v);
        if (u != v) {
            if (sz[u] < sz[v]) swap(u, v);
            sz[u] += sz[v];
            par[v] = u;
        }
    }
    void solve() {
        makeset();
        for (int i = 1; i <= m; i++) {
            int u = find(a[i].u), v = find(a[i].v);
            if (u != v) {
                adj1[a[i].u].emplace_back(a[i].v, min(length[a[i].u], length[a[i].v]));
                adj1[a[i].v].emplace_back(a[i].u, min(length[a[i].u], length[a[i].v]));
                join(a[i].u, a[i].v);
            }
        }
    }
} mst;

namespace cal {
    int up[N][lim + 1], weight[N][lim + 1], h[N];
    void dfs(int u, int par) {
        up[u][0] = par;
        for (int i = 1; i <= lim; i++) {
            up[u][i] = up[up[u][i - 1]][i - 1];
            weight[u][i] = min(weight[up[u][i - 1]][i - 1], weight[u][i - 1]);
        }
        for (auto [v, w] : adj1[u]) {
            if (v == par) continue;
            weight[v][0] = w;
            h[v] = h[u] + 1;
            dfs(v, u);
        }
    }
    int get(int u, int v) {
        if (u == v) return length[u];
        if (h[u] < h[v]) swap(u, v);
        int res = inf;
        for (int i = lim; i >= 0; i--) {
            if (h[u] - (1 << i) >= h[v]) {
                res = min(res, weight[u][i]);
                u = up[u][i];
            }
        }
        if (u == v) return res;
        for (int i = lim; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                res = min({res, weight[u][i], weight[v][i]});
                u = up[u][i];
                v = up[v][i];
            }
        }
        return min({res, weight[u][0], weight[v][0]});
    }
    void process() {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= lim; j++) weight[i][j] = inf;
        }
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].u >> a[i].v >> a[i].w;
        adj[a[i].u].emplace_back(a[i].v, a[i].w);
        adj[a[i].v].emplace_back(a[i].u, a[i].w);
    }
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> p[i];
    dijk();
    // for (int i = 1; i <= n; i++) cout << length[i] << ' ';
    sort(a + 1, a + m + 1, cmp);
    mst.solve();
    cal::process();
    cal::dfs(1, 0);
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        cout << cal::get(u, v) << '\n';
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:135:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
plan.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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