oj.uz

Submission #1111075

# Submission time Handle Problem Language Result Execution time Memory
1111075 2024-11-11T12:20:47 Z f0rizen Cities (BOI16_cities) C++17
0 / 100
 854 ms 22676 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int u, v, w;

    bool operator<(const Edge &p) {
        return w < p.w;
    }
};

struct DSU {
    vector<int> p, sz;

    DSU() {}
    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.resize(n, 1);
    }

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

    bool same(int u, int v) {
        return root(u) == root(v);
    }

    bool unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) {
            return false;
        }
        if (sz[u] > sz[v]) {
            swap(u, v);
        }
        p[u] = v;
        sz[v] += sz[u];
        return true;
    }
};

struct BinaryJumps {
    static const int lg = 17;

    vector<int> d;
    vector<vector<int>> up;

    BinaryJumps() {}
    BinaryJumps(int n) {
        d.resize(n);
        up.resize(lg, vector<int>(n, -1));
    }

    void add_leaf(int v, int p) {
        d[v] = d[p] + 1;
        up[0][v] = p;
        for (int i = 1; i < lg; ++i) {
            if (up[i - 1][v] != -1) {
                up[i][v] = up[i - 1][up[i - 1][v]];
            }
        }
    }

    int la(int v, int k) {
        for (int i = lg - 1; i >= 0; --i) {
            if (k >= (1 << i)) {
                k -= (1 << i);
                v = up[i][v];
            }
        }
        return v;
    }

    int lca(int u, int v) {
        if (d[u] < d[v]) {
            swap(u, v);
        }
        u = la(u, d[u] - d[v]);
        for (int i = lg - 1; i >= 0; --i) {
            if (up[i][u] != up[i][v]) {
                u = up[i][u];
                v = up[i][v];
            }
        }
        if (u == v) {
            return u;
        }
        return up[0][u];
    }

    int dist(int u, int v) {
        int w = lca(u, v);
        return d[u] + d[v] - 2 * d[w];
    }

    bool on_path(int u, int v, int a) {
        return dist(u, a) + dist(a, v) == dist(u, v);
    }
};

vector<vector<pair<int, int>>> g;
BinaryJumps tr;

void dfs(int v, int p = -1) {
    for (auto [u, w] : g[v]) {
        if (u != p) {
            tr.add_leaf(u, v);
            dfs(u, v);
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> a(k);
    cin >> a;
    for (auto &i : a) {
        --i;
    }
    vector<Edge> edg(m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        edg[i] = {u, v, w};
    }
    sort(edg.begin(), edg.end());
    DSU dsu(n);
    g.resize(n);
    vector<Edge> mst;
    for (auto [u, v, w] : edg) {
        if (dsu.unite(u, v)) {
            g[u].push_back({v, w});
            g[v].push_back({u, w});
            mst.push_back({u, v, w});
        }
    }
    tr = BinaryJumps(n);
    dfs(0);
    ll ans = 0;
    for (auto [u, v, w] : mst) {
        bool ok = false;
        for (auto i : a) {
            for (auto j : a) {
                if (tr.on_path(i, j, u) && tr.on_path(i, j, v)) {
                    ok = true;
                }
            }
        }
        if (ok) {
            ans += w;
        }
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 341 ms 22524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 22676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 854 ms 22268 KB Output isn't correct
2 Halted 0 ms 0 KB -