Submission #1069068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069068		manhlinh1501	Evacuation plan (IZhO18_plan)	C++17	100 / 100	338 ms	107408 KiB

plan

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 5e5 + 5;
using pii = pair<int, int>;
using pli = pair<i64, int>;
using pil = pair<int, i64>;
const int LOGN = 20;
const i64 oo64 = 1e18 + 5;

#define ALL(a) (a).begin(), (a).end()

struct edge {
    int u, v, w;
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};

struct DSU {
    int lab[MAXN];

    void init(int N) {
        for(int i = 1; i <= N; i++) lab[i] = -1;
    }

    int root(int u) {
        if(lab[u] < 0)
            return u;
        return lab[u] = root(lab[u]);
    }

    bool join(int u, int v) {
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }
} dsu;

int N, M, K, Q;
vector<pii> adj[MAXN];
edge e[MAXN];
int b[MAXN];
i64 dist[MAXN];
vector<edge> edges;
pil up[MAXN][LOGN];
vector<pil> g[MAXN];
int depth[MAXN];

void DFS(int u, int p) {
    for(auto [v, w] : g[u]) {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        up[v][0] = {u, w};
        for(int i = 1; i < LOGN; i++) {
            up[v][i].first = up[up[v][i - 1].first][i - 1].first;
            up[v][i].second = min(up[v][i - 1].second, up[up[v][i - 1].first][i - 1].second);
        }
        DFS(v, u);
    }
}
void dijkstra() {
    priority_queue<pli, vector<pli>, greater<pli>> Q;

    memset(dist, 0x3f, sizeof dist);

    for(int i = 1; i <= K; i++) {
        dist[b[i]] = 0;
        Q.emplace(dist[b[i]], b[i]);
    }

    while(!Q.empty()) {
        pli top = Q.top();
        Q.pop();
        int u = top.second;
        if(dist[u] != top.first) continue;
        for(auto [v, w] : adj[u]) {
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                Q.emplace(dist[v], v);
            }
        }
    }
}

i64 LCA(int u, int v) {
    i64 res = oo64;
    if(depth[u] != depth[v]) {
        if(depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        for(int i = 0; (1 << i) <= k; i++) {
            if(k >> i & 1) {
                res = min(res, up[u][i].second);
                u = up[u][i].first;
            }
        }
    }
    if(u == v) return res;
    int k = 31 - __builtin_clz(depth[u]);

    for(int i = k; i >= 0; i--) {
        if(up[u][i].first != up[v][i].first) {
            res = min(res, min(up[u][i].second, up[v][i].second));
            u = up[u][i].first;
            v = up[v][i].first;
        }
    }
    return min(res, min(up[u][0].second, up[v][0].second));
}

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for(int i = 1; i <= M; i++) {
        auto &[u, v, w] = e[i];
        cin >> u >> v >> w;
    }

    cin >> K;

    for(int i = 1; i <= K; i++) cin >> b[i];

    for(int i = 1; i <= M; i++) {
        auto [u, v, w] = e[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    dijkstra();

    for(int i = 1; i <= M; i++) {
        auto [u, v, w] = e[i];
        edges.emplace_back(u, v, min(dist[u], dist[v]));
    }

    sort(ALL(edges), [&](const edge a, const edge b) {
        return a.w > b.w;
    });

    dsu.init(N);

    for(auto [u, v, w] : edges) {
        if(dsu.join(u, v)) {
            g[u].emplace_back(v, w);
            g[v].emplace_back(u, w);
        }
    }

    DFS(1, 0);

    cin >> Q;
    while(Q--) {
        int S, T;
        cin >> S >> T;
        cout << LCA(S, T) << "\n";
    }

    return (0 ^ 0);
}

Compilation message (stderr)

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

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