結果
問題 | No.2504 NOT Path Painting |
ユーザー | 👑 emthrm |
提出日時 | 2023-08-12 19:28:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,741 bytes |
コンパイル時間 | 1,123 ms |
コンパイル使用メモリ | 97,860 KB |
実行使用メモリ | 11,024 KB |
最終ジャッジ日時 | 2024-11-29 23:58:45 |
合計ジャッジ時間 | 6,303 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 21 |
ソースコード
#include <cassert>#include <iostream>#include <tuple>#include <utility>#include <vector>namespace emthrm {std::pair<int, std::vector<int>> double_sweep(const std::vector<std::vector<int>>& graph) {const auto dfs1 = [&graph](auto dfs1, const int par, const int ver)-> std::pair<int, int> {std::pair<int, int> res{0, ver};for (const int e : graph[ver]) {if (e != par) {std::pair<int, int> child = dfs1(dfs1, ver, e);++child.first;if (child.first > res.first) res = child;}}return res;};const int s = dfs1(dfs1, -1, 0).second;const auto [diameter, t] = dfs1(dfs1, -1, s);std::vector<int> path{s};const auto dfs2 = [&graph, t, &path](auto dfs2, const int par, const int ver)-> bool {if (ver == t) return true;for (const int e : graph[ver]) {if (e != par) {path.emplace_back(e);if (dfs2(dfs2, ver, e)) return true;path.pop_back();}}return false;};assert(dfs2(dfs2, -1, s));return {diameter, path};}} // namespace emthrm// 【テストケースのチェック】// 木の直径を標準エラー出力に出力する。int main() {constexpr int kMaxT = 100000, kMaxN = 40000;int t;std::cin >> t;assert(1 <= t && t <= kMaxT);while (t--) {int n;std::cin >> n;assert(2 <= n && n <= kMaxN);std::vector<std::vector<int>> tree(n);for (int i = 0; i < n - 1; ++i) {int u, v;std::cin >> u >> v;assert(1 <= u && u <= n && 1 <= v && v <= n);--u; --v;tree[u].emplace_back(v);tree[v].emplace_back(u);}std::cerr << emthrm::double_sweep(tree).second.size() << '\n';}return 0;}