QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #863688 | #9881. Diverge and Converge | qL | Compile Error | / | / | C++14 | 2.7kb | 2025-01-19 21:16:20 | 2025-01-19 21:16:21 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <functional>
using i32 = int;
using edges = std::vector<std::pair<i32, i32>>;
signed main() noexcept {
i32 n;
scanf("%d", &n);
edges e1(n - 1), e2(n - 1);
auto edge = [](i32 x, i32 y) noexcept { return x < y ? std::make_pair(x, y) : std::make_pair(y, x); };
for (i32 i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), e1[i - 1] = edge(--u, --v);
for (i32 i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), e2[i - 1] = edge(--u, --v);
std::function<std::pair<edges, edges>(edges, edges)> solve = [&](edges e1, edges e2) noexcept -> std::pair<edges, edges> {
if (e1.empty()) return {};
std::vector<std::vector<i32>> G1(n), G2(n);
for (auto [u, v] : e1) G1[u].push_back(v), G1[v].push_back(u);
for (auto [u, v] : e2) G2[u].push_back(v), G2[v].push_back(u);
for (i32 x = 0; x < n; ++x)
if (G1[x].size() + G2[x].size() == 2) {
i32 a = G1[x][0], b = G2[x][0];
e1.erase(std::find(e1.begin(), e1.end(), edge(x, a)));
e2.erase(std::find(e2.begin(), e2.end(), edge(x, b)));
auto [t1, t2] = solve(e1, e2);
t1.emplace_back(edge(x, a)), t2.emplace_back(edge(x, b));
return {t1, t2};
} else if (G1[x].size() + G2[x].size() == 3) {
bool swapped = G1[x].size() > G2[x].size();
if (swapped) std::swap(G1, G2), std::swap(e1, e2);
i32 a = G1[x][0], b = G2[x][0], c = G2[x][1];
e1.erase(std::find(e1.begin(), e1.end(), edge(x, a)));
e2.erase(std::find(e2.begin(), e2.end(), edge(x, b)));
e2.erase(std::find(e2.begin(), e2.end(), edge(x, c)));
e2.emplace_back(edge(b, c));
auto [t1, t2] = solve(e1, e2);
i32 cur = std::find(t2.begin(), t2.end(), edge(b, c)) - t2.begin();
std::vector<std::vector<i32>> G3(n);
std::vector<bool> vis(n);
for (i32 i = 0; i != cur; ++i) {
auto [u, v] = t2[i];
G3[u].push_back(v), G3[v].push_back(u);
}
for (i32 i = t1.size() - 1; i != cur; ++i) {
auto [u, v] = t1[i];
G3[u].push_back(v), G3[v].push_back(u);
}
std::function<void(i32, i32)> dfs = [&](i32 x, i32 fa) noexcept {
vis[x] = true;
for (i32 y : G3[x])
if (y != fa) dfs(y, x);
};
auto [d, e] = t1[cur];
dfs(d, 0);
if (vis[a] != vis[b]) std::swap(b, c);
t2[cur] = edge(x, c);
t1.insert(t1.begin() + cur + 1, edge(x, a));
t2.insert(t2.begin() + cur + 1, edge(x, b));
if (swapped) std::swap(t1, t2);
return {t1, t2};
}
};
auto [t1, t2] = solve(e1, e2);
for (i32 i = 1; i < n; ++i) printf("%d%c", (std::find(e1.begin(), e1.end(), t1[i - 1]) - e1.begin()) + 1, " \n"[i == n - 1]);
for (i32 i = 1; i < n; ++i) printf("%d%c", (std::find(e2.begin(), e2.end(), t2[i - 1]) - e2.begin()) + 1, " \n"[i == n - 1]);
return 0;
}
详细
answer.code: In lambda function:
answer.code:16:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
16 | for (auto [u, v] : e1) G1[u].push_back(v), G1[v].push_back(u);
| ^
answer.code:17:27: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
17 | for (auto [u, v] : e2) G2[u].push_back(v), G2[v].push_back(u);
| ^
answer.code:21:47: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
21 | e1.erase(std::find(e1.begin(), e1.end(), edge(x, a)));
| ^~~~
| bind
answer.code:22:47: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
22 | e2.erase(std::find(e2.begin(), e2.end(), edge(x, b)));
| ^~~~
| bind
answer.code:23:38: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
23 | auto [t1, t2] = solve(e1, e2);
| ^
answer.code:30:47: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
30 | e1.erase(std::find(e1.begin(), e1.end(), edge(x, a)));
| ^~~~
| bind
answer.code:31:47: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
31 | e2.erase(std::find(e2.begin(), e2.end(), edge(x, b)));
| ^~~~
| bind
answer.code:32:47: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
32 | e2.erase(std::find(e2.begin(), e2.end(), edge(x, c)));
| ^~~~
| bind
answer.code:34:38: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
34 | auto [t1, t2] = solve(e1, e2);
| ^
answer.code:35:48: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
35 | i32 cur = std::find(t2.begin(), t2.end(), edge(b, c)) - t2.begin();
| ^~~~
| bind
answer.code:39:46: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
39 | auto [u, v] = t2[i];
| ^
answer.code:43:46: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
43 | auto [u, v] = t1[i];
| ^
answer.code:51:38: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
51 | auto [d, e] = t1[cur];
| ^
answer.code: In function ‘int main()’:
answer.code:61:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
61 | auto [t1, t2] = solve(e1, e2);
| ^
answer.code:62:58: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
62 | for (i32 i = 1; i < n; ++i) printf("%d%c", (std::find(e1.begin(), e1.end(), t1[i - 1]) - e1.begin()) + 1, " \n"[i == n - 1]);
| ^~~~
| bind
answer.code:63:58: error: ‘find’ is not a member of ‘std’; did you mean ‘bind’?
63 | for (i32 i = 1; i < n; ++i) printf("%d%c", (std::find(e2.begin(), e2.end(), t2[i - 1]) - e2.begin()) + 1, " \n"[i == n - 1]);
| ^~~~
| bind
answer.code:8:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
8 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
answer.code:11:48: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
11 | for (i32 i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), e1[i - 1] = edge(--u, --v);
| ~~~~~^~~~~~~~~~~~~~~~
answer.code:12:48: warning: igno...