Submission #90273

#	Time	Username	Problem	Language	Result	Execution time	Memory
90273		HardNut	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1184 ms	53544 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const long long INF = 1e9 + 5;
const int MAXN = 1e6;
const int base = 317;

typedef long long ll;

const ll bs = 1e5 + 1;
const ll mod = 998244353;

int n, m, up[21][N], res[21][N];
int dep[N], d[N], p[N], u[N], v[N];
vector <pair<int, int>> g[N];
vector <pair<int, pair<int, int>>> gr;
vector <int> gg[N];

void dfs(int v, int p = 0) {
    up[0][v] = p;
    res[0][v] = min(d[v], d[p]);
    for (int i = 1; i <= 20; i++) {
        up[i][v] = up[i - 1][up[i - 1][v]];
        res[i][v] = min(res[i - 1][v], res[i - 1][up[i - 1][v]]);
    }
    dep[v] = dep[p] + 1;
    for (auto to : gg[v]) {
        if (to != p)
            dfs(to, v);
    }
}

int ans(int u, int v) {
    if (dep[u] > dep[v])
        swap(u, v);
    int rs = INF;
    for (int i = 20; i >= 0; i--) {
        if (dep[u] <= dep[up[i][v]]) {
            rs = min(rs, res[i][v]);
            v = up[i][v];
        }
    }
    if (v == u)
        return rs;
    for (int i = 20; i >= 0; i--) {
        if (up[i][v] != up[i][u]) {
            rs = min(rs, res[i][v]);
            rs = min(rs, res[i][u]);
            v = up[i][v];
            u = up[i][u];
        }
    }
    return min(rs, min(res[0][v], res[0][u]));
}

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

void unite(int u, int v) {
    u = get(u);
    v = get(v);
    p[u] = v;
}

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int w;
        cin >> u[i] >> v[i] >> w;
        g[u[i]].push_back({v[i], w});
        g[v[i]].push_back({u[i], w});
    }
    int k;
    cin >> k;
    set <pair<int, int>> st;
    for (int i = 1; i <= n; i++) {
        d[i] = INF;
    }
    for (int i = 1; i <= k; i++) {
        int v;
        cin >> v;
        st.insert({0, v});
        d[v] = 0;
    }
    while (!st.empty()) {
        int v = (*st.begin()).second;
        st.erase(st.begin());
        for (auto it : g[v]) {
            int to = it.first, w = it.second;
            if (d[to] > d[v] + w) {
                st.erase({d[to], to});
                d[to] = d[v] + w;
                st.insert({d[to], to});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        for (int j = 0; j < g[i].size(); j++) {
            gr.push_back({min(d[g[i][j].first], d[i]), {i, g[i][j].first}});
        }
    }
    sort(gr.rbegin(), gr.rend());
    for (int i = 0; i < gr.size(); i++) {
        int v = gr[i].second.first, u = gr[i].second.second;
        if (get(v) != get(u)) {
            gg[u].push_back(v);
            gg[v].push_back(u);
            unite(v, u);
        }
    }
    for (int i = 0; i <= 20; i++) {
        for (int j = 0; j <= n; j++)
            res[i][j] = INF;
    }
    d[0] = INF;
    dfs(1);
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << ans(a, b) << "\n";
    }
    return 0;
}
/*

*/

Compilation message (stderr)

plan.cpp:70:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
plan.cpp: In function 'int main()':
plan.cpp:109:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++) {
                         ~~^~~~~~~~~~~~~
plan.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gr.size(); i++) {
                     ~~^~~~~~~~~~~

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