Submission #90457

#	Time	Username	Problem	Language	Result	Execution time	Memory
90457		adlet	Evacuation plan (IZhO18_plan)	C++17	0 / 100	1431 ms	58632 KiB

plan

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;

typedef long long ll;

const int LG = 20;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e9;
const double PI = acos(-1.0);

struct item {
    int w, x, y;
};

vector < item > e;

int n, m, k, q, p[N], lvl[N], up[N][LG + 5], mn[N][LG + 5];

int d[N];

vector < pair < int, int > > g[N], g1[N];

int get(int v) {
    return (v == p[v] ? v : p[v] = get(p[v]));
}

inline void unite(int v, int u) {
    v = get(v);
    u = get(u);
    if (rand() & 1)
        swap(v, u);
    if (v != u)
        p[u] = v;
}

int solve(int s, int t) {
    if (lvl[s] < lvl[t])
        swap(s, t);
    int ans = min(mn[s][0], mn[t][0]);
    for (int i = LG; i >= 0; --i) {
        if (lvl[up[s][i]] >= lvl[t]) {
            ans = min(mn[s][i], ans);
            s = up[s][i];
        }
    }
    if (s == t)
        return ans;
    for (int i = LG; i >= 0; --i) {
        if (up[s][i] != up[t][i]) {
            ans = min(mn[s][i], ans);
            ans = min(mn[t][i], ans);
            s = up[s][i];
            t = up[t][i];
        }
    }
    return min({ans, mn[s][0], mn[t][0]});
}

bool cmp(item a, item b) {
    return a.w < b.w;
}

inline void dfs(int v, int p = 0, int len = INF) {
    up[v][0] = p;
    mn[v][0] = len;
    lvl[v] = lvl[p] + 1;
    for (int i = 1; i <= LG; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
    }
    for (auto node : g1[v]) {
        int to = node.first, lenn = node.second;
        if (p != to)
            dfs(to, v, lenn);
    }
}

int main() {
    srand(time(NULL));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
        p[i] = i;
        for (int j = 0; j <= LG; ++j)
            mn[i][j] = INF;
    }
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[v].push_back({u, w});
        g[u].push_back({v, w});
    }
    cin >> k;
    set < pair < int, int > > st;
    for (int i = 1, x; i <= k; ++i) {
        cin >> x;
        d[x] = 0;
        st.insert({0, x});
    }
    while (!st.empty()) {
        int x = st.begin() -> second;
        st.erase(st.begin());
        for (auto node : g[x]) {
            int to = node.first, len = node.second;
            if (d[to] > d[x] + len) {
                st.erase({d[to], to});
                d[to] = d[x] + len;
                st.insert({d[to], to});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (auto node : g[i]) {
            int to = node.first;
            e.push_back({-1 *  min(d[to], d[i]), i, to});
        }
    }
    sort(e.begin(), e.end(), &cmp);
    for (auto ver : e) {
        int x = ver.x, y = ver.y, w = -ver.w;
        if (get(x) != get(y)) {
            g1[x].push_back({y, w});
            g1[y].push_back({x, w});
            unite(x, y);
        }
    }
    dfs(n);
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int s, t;
        cin >> s >> t;
        cout << solve(s, t) << "\n";
    }
}

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