QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168760#7103. Red Black TreeFu_suCompile Error//C++175.1kb2023-09-08 21:19:032023-09-08 21:19:04

Judging History

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

  • [2023-09-08 21:19:04]
  • 评测
  • [2023-09-08 21:19:03]
  • 提交

answer

#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

std::vector<std::vector<std::pair<int, long long>>> E;
std::vector<char> vis;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  E.resize(1e5 + 5);
  vis.resize(1e5 + 5);
  for (std::cin >> T; T; --T) {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<int> col(n + 1);
    for (int r, i = 1; i <= m; ++i) {
      std::cin >> r; col[r] = 1;
    }
    std::vector<std::vector<std::pair<int, int>>> e(n + 1);
    for (int i = 1, u, v, w; i < n; ++i) {
      std::cin >> u >> v >> w;
      e[u].push_back({v, w});
      e[v].push_back({u, w});
    }
    int vistime = 0;
    std::vector<int> anc(n + 1), stk, dfn(n + 1), euler, lastpos(n + 1), height(n + 1);
    std::vector<long long> sum(n + 1), ans(n + 1);
    auto dfs = [&](auto &&self, const int u) -> void {
      if (col[u] == 1) stk.push_back(u);
      dfn[u] = ++vistime;
      anc[u] = stk.back();
      ans[u] = sum[u] - sum[anc[u]];
      euler.push_back(u);
      lastpos[u] = euler.size() - 1;
      for (auto [v, w] : e[u]) if (anc[v] == 0) {
        height[v] = height[u] + 1;
        sum[v] = sum[u] + w;
        self(self, v);
        euler.push_back(u);
        lastpos[u] = euler.size() - 1;
      }
      if (col[u] == 1) stk.pop_back();
    };
    dfs(dfs, 1);
    auto minNode = [&](const int u, const int v) {
      if (height[u] < height[v]) return u;
      else return v;
    };
    std::vector ST(18, std::vector<int>(2 * (n + 3)));
    for (int i = 0; i < euler.size(); ++i) ST[0][i] = euler[i];
    for (int i = 0; i < 17; ++i) {
      for (int l = 0; l < euler.size(); ++l) {
        int r = l + (1 << (i + 1)) - 1;
        if (r >= euler.size()) break;
        int mid = l + (1 << (i));
        ST[i + 1][l] = minNode(ST[i][l], ST[i][mid]);
      }
    }
    auto LCA = [&](int u, int v) {
      int x = lastpos[u], y = lastpos[v];
      if (x > y) std::swap(x, y);
      int len = y - x + 1;
      return minNode(ST[log2(len)][x], ST[log2(len)][y - (1 << signed(log2(len))) + 1]);
    };
    auto dist = [&](int u, int v) {
      if (height[u] < height[v]) std::swap(u, v);
      return sum[u] - sum[v];
    };
    auto build_virtual_tree = [&](std::vector<int> &h, auto &e) {
      std::vector<int> a;
      std::sort(h.begin(), h.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
      for (int i = 0; i < h.size(); ++i) {
        a.push_back(h[i]);
        if (i + 1 != h.size()) {
          a.push_back(LCA(h[i], h[i + 1]));
        }
      }
      std::sort(a.begin(), a.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
      a.erase(std::unique(a.begin(), a.end()), a.end());
      std::vector<int> res;
      for (int i = 0; i < a.size() - 1; ++i) {
        int lc = LCA(a[i], a[i + 1]);
        e[lc].push_back({a[i + 1], dist(a[i + 1], lc)});
        e[a[i + 1]].push_back({lc, dist(a[i + 1], lc)});
        res.push_back(lc);
        res.push_back({a[i + 1]});
      }
      std::sort(res.begin(), res.end());
      res.erase(std::unique(res.begin(), res.end()), res.end());
      return res;
    };
    std::vector<int> iskey(n + 1);
    for (int k, x; q; --q) {
      std::vector<int> h;
      std::multiset<long long> s;
      long long res = 0;
      for (std::cin >> k; k; --k) {
        std::cin >> x;
        h.push_back(x);
        iskey[x] = 1;
        res = std::max(res, ans[x]);
        
      }
      int ances = 0;
      long long maxdep = 0;
      std::vector<int> keyNodes;
      for (auto u : h) if (ans[u] == res) {
        maxdep = sum[u];
        keyNodes.push_back(u);
        if (ances == 0) ances = anc[u];
        else if (anc[u] != ances) ances = -1;
      }
      if (ances == -1) {
        for (auto u : h) iskey[u] = 0;
        std::cout << res << '\n';
        continue;
      }
      int resmax = 0;
      for (auto u : h) if (anc[u] == ances) {
        s.insert(ans[u]);
      } else {
        resmax = std::max(resmax, ans[u]);
      }
      k = h.size();
      for (int i = 0; i < k; ++i) h.push_back(anc[h[i]]);
      auto nodes = build_virtual_tree(h, E);
      std::sort(keyNodes.begin(), keyNodes.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
      int lca = keyNodes[0];
      for (int i = 1; i < keyNodes.size(); ++i) lca = LCA(keyNodes[i], lca);
      auto dfs2 = [&](auto &&self, int u) -> void {
        vis[u] = 1;
        if (iskey[u] && anc[u] == ances) s.erase(s.find(ans[u]));
        for (auto [v, w] : E[u]) if (height[v] > height[u] && vis[v] == 0 && col[v] == 0) {
          self(self, v);
        }
      };
      while (lca != ances) {
        dfs2(dfs2, lca);
        res = std::min(res, std::max({maxdep - sum[lca], (s.size() ? *s.rbegin() : 0ll), resmax}));
        for (auto [v, w] : E[lca]) if (height[v] < height[lca]) {
          lca = v; break;
        }
      }
      for (auto u : nodes) E[u].clear();
      std::cout << res << '\n';
      for (auto u : nodes) iskey[u] = vis[u] = 0;
    }
  }
}


Details

answer.code: In function ‘int main()’:
answer.code:127:26: error: no matching function for call to ‘max(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)’
  127 |         resmax = std::max(resmax, ans[u]);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_tree.h:63,
                 from /usr/include/c++/11/set:60,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:127:26: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’})
  127 |         resmax = std::max(resmax, ans[u]);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_tree.h:63,
                 from /usr/include/c++/11/set:60,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
answer.code:127:26: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type’ {aka ‘long long int’})
  127 |         resmax = std::max(resmax, ans[u]);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from answer.code:6:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)’
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
answer.code:127:26: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  127 |         resmax = std::max(resmax, ans[u]);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from answer.code:6:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)’
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
answer.code:127:26: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  127 |         resmax = std::max(resmax, ans[u]);
      |                  ~~~~~~~~^~~~~~~~~~~~~~~~
answer.code:144:37: error: no matching function for call to ‘max(<brace-enclosed initializer list>)’
  144 |         res = std::min(res, std::max({maxdep - sum[lca], (s.size() ? *s.rbegin() : 0ll), resmax}));
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_tree.h:63,
                 from /usr/include/c++/11/set:60,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
answer.code:144:37: note:   candidate expects 2 arguments, 1 provided
  144 |         res = std::min(res, std::max({maxdep - sum[lca], (s.size() ? *s.rbegin() : 0ll), resmax}));
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_tree.h:63,
                 from /usr/include/c++/11/set:60,
                 from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
answer.code:144:37: note:   candidate expects 3 arguments, 1 provided
  144 |         res = std::min(res, std::max({maxdep - sum[lca], (s.size() ? *s.rbegin() : 0ll), resmax}));
      |                             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/algorithm:62,
                 from answer.code:6:
/usr/include/c++/11/bit...