Submission #1101888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101888		susanthenerd	Roadside Advertisements (NOI17_roadsideadverts)	C++17	0 / 100	54 ms	9116 KiB

roadsideadverts

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
constexpr int LOG = 18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> h(n + 1), d(n + 1);
    vector<vector<pair<int, int> > > adj(n + 1);
    vector anc(LOG + 1, vector<int>(n + 1));


    for (int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u + 1].emplace_back(v + 1, w);
        adj[v + 1].emplace_back(u + 1, w);
    }

    auto dfs = [&](auto &&self, int u, int p) -> void {
        anc[0][u] = p;

        for (int i = 1; i <= LOG; ++i)
            anc[i][u] = anc[i - 1][anc[i - 1][u]];

        for (auto &[v, w]: adj[u]) {
            if (v == p) continue;

            d[v] = d[u] + 1;
            h[v] = h[u] + w;
            self(self, v, u);
        }
    };

    dfs(dfs, 1, 0);

    auto lca = [&](int a, int b) {
        if (d[a] < d[b]) swap(a, b);

        for (int i = LOG; i >= 0; --i) {
            if (d[a] - (1 << i) >= d[b])
                a = anc[i][a];
        }

        if (a == b) {
            return a;
        } else {
            for (int i = LOG; i >= 0; --i) {
                if (anc[i][a] != anc[i][b]) {
                    a = anc[i][a];
                    b = anc[i][b];
                }
            }

            return anc[0][a];
        }
    };


    int q;
    cin >> q;


    while (q--) {
        vector<int> arr(5);
        for (auto &it: arr) {
            cin >> it;
            it += 1;
        }
        sort(arr.begin(), arr.end(), [&](int a, int b) {
            return d[a] < d[b];
        });

        int lca5 = arr[0];
        for (int i = 1; i < 5; ++i)
            lca5 = lca(lca5, arr[i]);
        int ans = h[arr[0]] - h[lca5];

        for (int i = 1; i < 5; ++i) {
            ans += h[arr[i]] - h[lca(arr[i], arr[i - 1])];
        }

        cout << ans << '\n';
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 40
• Subtask 4: 0 / 30