QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694814#5439. Meet in the Middlezfs732Compile Error//C++144.3kb2024-10-31 18:43:162024-10-31 18:43:20

Judging History

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

  • [2024-10-31 18:43:20]
  • 评测
  • [2024-10-31 18:43:16]
  • 提交

answer

#include <bits/stdc++.h>
#include <ostream>

struct Graph {
  int tot;
  std::vector<int> ord, edp;
  std::vector<long long> dist;
  std::vector<std::vector<std::pair<int, int>>> graph;
  std::vector<std::vector<int>> mi;

  int Cmp(int x, int y) const { return ord[x] < ord[y] ? x : y; }

  void DFS(int u, int prt) {
    mi[0][ord[u] = tot++] = prt;
    for (auto [v, w]: graph[u]) {
      if (v != prt) {
        dist[v] = dist[u] + w;
        DFS(v, u);
      }
    }
  }

  int LCA(int u, int v) const {
    if (u == v) { return u; }
    if ((u = ord[u]) > (v = ord[v])) { std::swap(u, v); }
    int k = std::__lg(v - u++);
    return Cmp(mi[k][u], mi[k][v - (1 << k) + 1]);
  }

  long long Dist(int u, int v) const {
    return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
  }

  explicit Graph(const std::vector<std::vector<std::pair<int, int>>> &graph)
      : tot(0), graph(graph) {
    int N = (int) graph.size(), M = std::__lg(N);
    ord.resize(N), edp.resize(N), dist.resize(N);
    mi.resize(M + 1, std::vector<int>(N)), DFS(0, -1);
    for (int j = 1; j <= M; j++) {
      for (int i = 0; i + (1 << j) <= N; i++) {
        mi[j][i] = Cmp(mi[j - 1][i], mi[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
};

Graph *G;

struct Node {
  int p;
  long long w;

  friend std::ostream &operator<<(std::ostream &os, const Node &obj) {
    return os << "p: " << obj.p << " w: " << obj.w;
  }

  friend auto Dist(Node a, Node b) { return G->Dist(a.p, b.p) + a.w + b.w; }
};

struct Info {
  Node a, b;

  friend std::ostream &operator<<(std::ostream &os, const Info &obj) {
    return os << "a: " << obj.a << " b: " << obj.b;
  }

  Info operator+(long long o) {
    Info ret = *this;
    ret.a.w += o, ret.b.w += o;
    return ret;
  }

  auto operator+(Node x) const {
    auto d1 = Dist(a, b);
    auto d2 = Dist(a, x);
    auto d3 = Dist(b, x);
    if (d1 >= std::max(d2, d3)) { return *this; }
    return d2 > d3 ? Info(a, x) : Info(b, x);
  }

  auto operator+(Info x) const { return *this + x.a + x.b; }
};

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

  int test = 1;
  while (test--) {
    int N, Q;
    std::cin >> N;
    std::vector graph(2, std::vector(N, std::vector<std::pair<int, int>>()));

    for (int o = 0; o < 2; o++) {
      for (int i = 1, u, v, w; i < N; i++) {
        std::cin >> u >> v >> w, u--, v--;
        graph[o][u].emplace_back(v, w);
        graph[o][v].emplace_back(u, w);
      }
    }

    Graph g0(graph[0]), g1(graph[1]);
    G = &g1;

    std::cin >> Q;
    std::vector<long long> ans(Q);
    std::vector buc(N, std::vector<std::pair<int, int>>());

    for (int i = 0; i < Q; i++) {
      int x, y;
      std::cin >> x >> y, x--, y--;
      buc[x].emplace_back(y, i);
    }

    std::vector<Info> s(N);
    std::vector<long long> dist(N);

    std::function<void(int, int)> DFS1 = [&](int u, int prt) {
      Node cur(u, dist[u]);
      s[u] = Info(cur, cur);
      for (auto [v, w]: graph[0][u]) {
        if (v != prt) {
          dist[v] = dist[u] + w;
          DFS1(v, u), s[u] = s[u] + s[v];
        }
      }
    };

    DFS1(0, -1);

    std::function<void(int, int, Info)> DFS2 = [&](int u, int prt, Info ps) {
      ps = ps + Node(u, -dist[u]);
      Info best = ps;
      std::vector<int> son;
      std::vector<Info> is;
      for (auto [v, w]: graph[0][u]) {
        if (v != prt) {
          son.emplace_back(v), is.emplace_back(s[v] + (-2 * dist[u]));
          best = best + is.back();
        }
      }
      for (auto [y, id]: buc[u]) {
        auto [a, b] = best;
        ans[id] = std::max(ans[id], g0.Dist(u, a.p) + g1.Dist(y, a.p));
        ans[id] = std::max(ans[id], g0.Dist(u, b.p) + g1.Dist(y, b.p));
      }
      int M = (int) son.size();
      auto pre = is, suf = is;
      for (int i = 1; i < M; i++) { pre[i] = pre[i - 1] + pre[i]; }
      for (int i = M - 1; i > 0; i--) { suf[i - 1] = suf[i - 1] + suf[i]; }
      for (int i = 0; i < M; i++) {
        int v = son[i];
        if (v != prt) {
          Info sp = ps;
          if (i) { sp = sp + pre[i - 1]; }
          if (i + 1 < M) { sp = sp + suf[i + 1]; }
          DFS2(v, u, sp);
        }
      }
    };

    DFS2(0, -1, {});

    for (auto v: ans) { std::cout << v << '\n'; }
  }

  return 0;
}

Details

answer.code: In member function ‘void Graph::DFS(int, int)’:
answer.code:15:15: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   15 |     for (auto [v, w]: graph[u]) {
      |               ^
answer.code: In member function ‘auto Info::operator+(Node) const’:
answer.code:78:31: error: no matching function for call to ‘Info::Info(const Node&, Node&)’
   78 |     return d2 > d3 ? Info(a, x) : Info(b, x);
      |                               ^
answer.code:60:8: note: candidate: ‘Info::Info()’
   60 | struct Info {
      |        ^~~~
answer.code:60:8: note:   candidate expects 0 arguments, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(const Info&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(Info&&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code:78:44: error: no matching function for call to ‘Info::Info(const Node&, Node&)’
   78 |     return d2 > d3 ? Info(a, x) : Info(b, x);
      |                                            ^
answer.code:60:8: note: candidate: ‘Info::Info()’
   60 | struct Info {
      |        ^~~~
answer.code:60:8: note:   candidate expects 0 arguments, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(const Info&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(Info&&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code: In function ‘int main()’:
answer.code:92:17: error: missing template arguments before ‘graph’
   92 |     std::vector graph(2, std::vector(N, std::vector<std::pair<int, int>>()));
      |                 ^~~~~
answer.code:97:9: error: ‘graph’ was not declared in this scope; did you mean ‘Graph’?
   97 |         graph[o][u].emplace_back(v, w);
      |         ^~~~~
      |         Graph
answer.code:102:14: error: ‘graph’ was not declared in this scope; did you mean ‘Graph’?
  102 |     Graph g0(graph[0]), g1(graph[1]);
      |              ^~~~~
      |              Graph
answer.code:107:17: error: missing template arguments before ‘buc’
  107 |     std::vector buc(N, std::vector<std::pair<int, int>>());
      |                 ^~~
answer.code:112:7: error: ‘buc’ was not declared in this scope
  112 |       buc[x].emplace_back(y, i);
      |       ^~~
answer.code: In lambda function:
answer.code:119:26: error: no matching function for call to ‘Node::Node(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)’
  119 |       Node cur(u, dist[u]);
      |                          ^
answer.code:49:8: note: candidate: ‘Node::Node()’
   49 | struct Node {
      |        ^~~~
answer.code:49:8: note:   candidate expects 0 arguments, 2 provided
answer.code:49:8: note: candidate: ‘constexpr Node::Node(const Node&)’
answer.code:49:8: note:   candidate expects 1 argument, 2 provided
answer.code:49:8: note: candidate: ‘constexpr Node::Node(Node&&)’
answer.code:49:8: note:   candidate expects 1 argument, 2 provided
answer.code:120:27: error: no matching function for call to ‘Info::Info(Node&, Node&)’
  120 |       s[u] = Info(cur, cur);
      |                           ^
answer.code:60:8: note: candidate: ‘Info::Info()’
   60 | struct Info {
      |        ^~~~
answer.code:60:8: note:   candidate expects 0 arguments, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(const Info&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code:60:8: note: candidate: ‘constexpr Info::Info(Info&&)’
answer.code:60:8: note:   candidate expects 1 argument, 2 provided
answer.code:121:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  121 |       for (auto [v, w]: graph[0][u]) {
      |                 ^
answer.code: In lambda function:
answer.code:132:33: error: no matching function for call to ‘Node::Node(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type)’
  132 |       ps = ps + Node(u, -dist[u]);
      |                                 ^
answer.code:49:8: note: candidate: ‘Node::Node()’
   49 | struct Node {
      |        ^~~~
answer.code:49:8: note:   candidate expects 0 arguments, 2 provided
answer.code:49:8: note: candidate: ‘constexpr Node::Node(const Node&)’
answer.code:49:8: note:   candidate expects 1 argument, 2 provided
answer.code:49:8: note: candidate: ‘constexpr Node::Node(Node&&)’
answer.code:49:8: note:   candidate expects 1 argument, 2 provided
answer.code:136:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  136 |       for (auto [v, w]: graph[0][u]) {
      |                 ^
answer.code:142:17: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  142 |       for (auto [y, id]: buc[u]) {
      ...