QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694814 | #5439. Meet in the Middle | zfs732 | Compile Error | / | / | C++14 | 4.3kb | 2024-10-31 18:43:16 | 2024-10-31 18:43:20 |
Judging History
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]) { ...