QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#779904#7103. Red Black TreergnerdplayerCompile Error//C++234.1kb2024-11-24 22:43:212024-11-24 22:43:21

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 22:43:21]
  • 评测
  • [2024-11-24 22:43:21]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

struct HLD {
    int n, cur = 0;
    vector<int> sz, top, dep, par, tin, tout, seq;
    vector<vector<int>> adj;
    HLD(int n) : n(n), sz(n, 1), top(n), dep(n), par(n), tin(n), tout(n), seq(n), adj(n) {}
    void add_edge(int u, int v) { adj[u].push_back(v), adj[v].push_back(u); }
    void build(int root = 0) {
        top[root] = root, dep[root] = 0, par[root] = -1;
        dfs1(root), dfs2(root);
    }
    void dfs1(int u) {
        if (auto it = find(adj[u].begin(), adj[u].end(), par[u]); it != adj[u].end()) {
            adj[u].erase(it);
        }
        for (auto &v : adj[u]) {
            par[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            sz[u] += sz[v];
            if (sz[v] > sz[adj[u][0]]) { swap(v, adj[u][0]); }
        }
    }
    void dfs2(int u) {
        tin[u] = cur++;
        seq[tin[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        tout[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = par[top[u]];
            } else {
                v = par[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
    int jump(int u, int k) {
        if (dep[u] < k) { return -1; }
        int d = dep[u] - k;
        while (dep[top[u]] > d) { u = par[top[u]]; }
        return seq[tin[u] - dep[u] + d];
    }
    // u is v's ancestor
    bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tin[v] < tout[u]; }
    // root's parent is itself
    int rooted_parent(int r, int u) {
        if (r == u) { return u; }
        if (is_ancestor(r, u)) { return par[u]; }
        auto it = upper_bound(adj[u].begin(), adj[u].end(), r, [&](int x, int y) {
            return tin[x] < tin[y];
        }) - 1;
        return *it;
    }
    // rooted at u, v's subtree size
    int rooted_size(int r, int u) {
        if (r == u) { return n; }
        if (is_ancestor(u, r)) { return sz[u]; }
        return n - sz[rooted_parent(r, u)];
    }
    int rooted_lca(int r, int a, int b) { return lca(a, b) ^ lca(a, r) ^ lca(b, r); }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;

    auto solve = [&]() {
        int n, m, q;
        cin >> n >> m >> q;

        constexpr i64 inf = 1e18;
        vector<i64> cost(n, inf);
        for (int i = 0; i < m; i++) {
            int u;
            cin >> u;
            cost[--u] = 0;
        }
        cost[0] = 0;

        vector<vector<pair<int, int>>> adj(n);
        HLD hld(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            u--, v--;
            adj[u].emplace_back(v, w);
            adj[v].emplace_back(u, w);
            hld.add_edge(u, v);
        }
        hld.build();

        auto dfs = [&](this auto dfs, int u) -> void {
            for (auto [v, w] : adj[u]) {
                if (v != hld.par[u]) {
                    cost[v] = min(cost[v], cost[u] + w);
                    dfs(v);
                }
            }
        };
        dfs(0);

        for (int i = 0; i < q; i++) {
            int k;
            cin >> k;
            vector<int> a(k);
            for (int j = 0; j < k; j++) {
                cin >> a[j];
                a[j]--;
            }
            sort(a.begin(), a.end(), [&](int u, int v) { return cost[u] > cost[v]; });

            i64 ans = cost[a[0]];
            int lca = a[0];
            i64 mx = 0;

            for (int j = 0; j < k; j++) {
                lca = hld.lca(lca, a[j]);
                mx = max(mx, cost[a[j]]);
                ans = min(ans, max(j == k - 1 ? 0 : cost[a[j + 1]], mx - cost[lca]));
            }

            cout << ans << '\n';
        }
    };
    
    while (t--) {
        solve();
    }
    
    return 0;
}

詳細信息

answer.code: In lambda function:
answer.code:105:24: error: expected identifier before ‘this’
  105 |         auto dfs = [&](this auto dfs, int u) -> void {
      |                        ^~~~
answer.code:105:24: error: expected ‘,’ or ‘...’ before ‘this’
answer.code: In lambda function:
answer.code:106:36: error: ‘u’ was not declared in this scope
  106 |             for (auto [v, w] : adj[u]) {
      |                                    ^
answer.code:109:21: error: use of ‘dfs’ before deduction of ‘auto’
  109 |                     dfs(v);
      |                     ^~~