結果
問題 | No.2427 Tree Distance Two |
ユーザー | nono00 |
提出日時 | 2023-08-18 21:45:27 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 670 ms / 2,000 ms |
コード長 | 5,219 bytes |
コンパイル時間 | 3,766 ms |
コンパイル使用メモリ | 253,804 KB |
実行使用メモリ | 38,272 KB |
最終ジャッジ日時 | 2024-05-06 03:43:25 |
合計ジャッジ時間 | 14,815 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 670 ms
29,184 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 621 ms
29,184 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 510 ms
27,948 KB |
testcase_08 | AC | 594 ms
31,232 KB |
testcase_09 | AC | 529 ms
27,976 KB |
testcase_10 | AC | 527 ms
28,544 KB |
testcase_11 | AC | 558 ms
27,896 KB |
testcase_12 | AC | 545 ms
28,132 KB |
testcase_13 | AC | 620 ms
28,256 KB |
testcase_14 | AC | 491 ms
38,272 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 12 ms
5,376 KB |
testcase_21 | AC | 16 ms
5,376 KB |
testcase_22 | AC | 5 ms
5,376 KB |
testcase_23 | AC | 3 ms
5,376 KB |
testcase_24 | AC | 13 ms
5,376 KB |
testcase_25 | AC | 126 ms
9,984 KB |
testcase_26 | AC | 340 ms
19,200 KB |
testcase_27 | AC | 235 ms
14,848 KB |
testcase_28 | AC | 523 ms
27,264 KB |
testcase_29 | AC | 494 ms
24,192 KB |
testcase_30 | AC | 331 ms
18,816 KB |
testcase_31 | AC | 201 ms
13,440 KB |
testcase_32 | AC | 352 ms
18,688 KB |
testcase_33 | AC | 315 ms
16,896 KB |
testcase_34 | AC | 80 ms
7,552 KB |
ソースコード
#include <bits/stdc++.h> // graph/graph-template.hpp // graph/graph.hpp #include <cassert> #include <vector> // graph/edge.hpp namespace nono { // brief: // - Edge構造体 // // tparam: // - `T`: 重みの型 // // note: // - `from`, `to`, `weight` がないと、他のライブラリが壊れる template <class T = int> struct Edge { using value_type = T; int from; int to; T weight; int index; // brief: // - Edgeコンストラクタ Edge(int from, int to, const T& weight = 1, int index = -1) : from(from), to(to), weight(weight), index(index) {} friend auto operator<=>(const Edge<T>& lhs, const Edge<T>& rhs) { return lhs.weight <=> rhs.weight; } }; } // namespace nono namespace nono { // brief: // - グラフ構造体 // // tparam: // - `T`: 辺の重みの型 // - `directed`: 有向かどうか // // note: // - 有向グラフのaliasとして `DiGraph` が存在する // - 以下の条件が満たさないと壊れる // \ \ 1. `size()` が頂点数を返す // \ \ 2. `operator[]` が `range-based for` に対応している template <class T = int, bool directed = false> class Graph { using EdgeType = Edge<T>; using EdgesType = std::vector<EdgeType>; public: using value_type = EdgesType; Graph() = default; explicit Graph(int vertex_size) : vertex_size_(vertex_size), edge_size_(0), adj_list_(vertex_size) {} Graph(int vertex_size, const std::vector<EdgeType>& edges) : vertex_size_(vertex_size), edge_size_(0), adj_list_(vertex_size) { for (const auto& e: edges) { adj_list_[e.from].emplace_back(e); } } // brief: // - 頂点数を取得する int size() const { return vertex_size_; } // brief: // - 頂点 `i` に隣接する頂点を取得する const std::vector<EdgeType>& operator[](int i) const { return adj_list_[i]; } // brief: // - 頂点 `i` に隣接する頂点を取得する std::vector<EdgeType>& operator[](int i) { return adj_list_[i]; } // brief: // - グラフに辺を追加する // // note: // - weightのデフォルト値は1 void add_edge(int from, int to, T weight = static_cast<T>(1), int index = -1) { adj_list_[from].emplace_back(from, to, weight, index); if (not directed) adj_list_[to].emplace_back(to, from, weight, index); edge_size_++; } // brief: // - 頂点 `i` の次数を取得する // // note: // - 有向グラフの場合、出次数を取得する int degree(int i) const { return adj_list_[i].size(); } // brief: // - 頂点の次数の配列を取得する // // note: // - 有向グラフの場合、出次数を取得する std::vector<int> degree() const { std::vector<int> result(vertex_size_); for (int i = 0; i < vertex_size_; i++) { result[i] = adj_list_[i].size(); } return result; } // brief: // - 辺の配列に取得する // // note: // - 単純グラフでないと壊れる std::vector<EdgeType> to_edges() const { std::vector<EdgeType> edges(edge_size_); int count = 0; for (int u = 0; u < vertex_size_; u++) { for (const auto& e: adj_list_[u]) { if (directed || e.from <= e.to) { edges[count] = e; count++; } } } return edges; } private: int vertex_size_; int edge_size_; std::vector<std::vector<EdgeType>> adj_list_; }; // brief: // - 有向グラフ構造体 // // tparam: // - `T`: 辺の重みの型 // // note: // - `Graph` のalias template <class T = int> using DiGraph = Graph<T, true>; } // namespace nono namespace nono { void solve() { int n; std::cin >> n; Graph tree(n); for (int i = 0; i < n - 1; i++) { int u, v; std::cin >> u >> v; u--; v--; tree.add_edge(u, v); } std::vector<int> parent(n); std::vector<int> child(n); std::vector<int> depth(n); auto dfs = [&](const auto& dfs, const auto& graph, int u, int p) -> void { parent[u] = p; for (const auto& e: graph[u]) { if (e.to == p) continue; depth[e.to] = depth[e.from] + 1; dfs(dfs, graph, e.to, e.from); child[u]++; } }; dfs(dfs, tree, 0, -1); for (int i = 0; i < n; i++) { int ans = 0; if (depth[i] >= 2) { ans++; } if (parent[i] != -1) { ans += child[parent[i]] - 1; } for (const auto& e: tree[i]) { if (e.to == parent[i]) continue; ans += child[e.to]; } std::cout << ans << std::endl; } } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); std::cout << std::fixed << std::setprecision(15); int t = 1; // std::cin >> t; while (t--) nono::solve(); }