제출 #90269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90269		HardNut	Evacuation plan (IZhO18_plan)	C++17	22 / 100	794 ms	68404 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], cnt;
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 rise(int v, int pr) {
    int ans = d[v];
    for (int i = 20; i >= 0; i--) {
        if (dep[pr] <= dep[up[i][v]]) {
            ans = min(ans, res[i][v]);
            v = up[i][v];
        }
    }
    return ans;
}

int lca(int a, int b) {
    if (dep[a] > dep[b])
        swap(a, b);
    for (int i = 20; i >= 0; i--) {
        if (dep[a] <= dep[up[i][b]]) {
            b = up[i][b];
        }
    }
    if (a == b)
        return a;
    for (int i = 20; i >= 0; i--) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

int ans(int u, int v) {
    int lc = lca(u, v);
    return min({rise(u, lc), rise(v, lc)});
}

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

void unite(int u, int v, int w) {
    int uu = u, vv = v;
    u = get(u);
    v = get(v);
    if (u == v)
        return;
    cnt++;
    if (cnt > n - 1) {
        assert(0);
    }
    gg[uu].push_back(vv);
    gg[vv].push_back(uu);
    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.begin(), gr.end());
    reverse(gr.begin(), gr.end());
    for (int i = 0; i < gr.size(); i++) {
        unite(gr[i].second.first, gr[i].second.second, gr[i].first);
    }
    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 << min({ans(a, b), d[a], d[b]}) << "\n";
    }
    return 0;
}
/**
6 5
1 3 9
2 3 3
3 4 5
4 5 6
5 6 7
1
1
1
6 2
*/

컴파일 시 표준 에러 (stderr) 메시지

plan.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
plan.cpp: In function 'int main()':
plan.cpp:130:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < g[i].size(); j++) {
                         ~~^~~~~~~~~~~~~
plan.cpp:136: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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46