結果
問題 |
No.3113 The farthest point
|
ユーザー |
![]() |
提出日時 | 2025-04-18 21:29:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,852 bytes |
コンパイル時間 | 5,505 ms |
コンパイル使用メモリ | 332,456 KB |
実行使用メモリ | 40,960 KB |
最終ジャッジ日時 | 2025-04-18 21:29:38 |
合計ジャッジ時間 | 9,114 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 WA * 13 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; template< typename T = int > struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { return to; } }; template< typename T = int > struct Graph { vector< vector< Edge< T > > > g; int es; Graph() = default; explicit Graph(int n) : g(n), es(0) {} size_t size() const { return g.size(); } void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); } void add_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es); g[to].emplace_back(to, from, cost, es++); } void read(int M, int padding = -1, bool weighted = false, bool directed = false) { for(int i = 0; i < M; i++) { int a, b; cin >> a >> b; a += padding; b += padding; T c = T(1); if(weighted) cin >> c; if(directed) add_directed_edge(a, b, c); else add_edge(a, b, c); } } inline vector< Edge< T > > &operator[](const int &k) { return g[k]; } inline const vector< Edge< T > > &operator[](const int &k) const { return g[k]; } }; template< typename T = int > using Edges = vector< Edge< T > >; template< typename T = int > struct TreeDiameter : Graph< T > { public: using Graph< T >::Graph; using Graph< T >::g; vector< Edge< T > > path; T build() { to.assign(g.size(), -1); auto p = dfs(0, -1); auto q = dfs(p.second, -1); int now = p.second; while(now != q.second) { for(auto &e : g[now]) { if(to[now] == e.to) { path.emplace_back(e); } } now = to[now]; } return q.first; } explicit TreeDiameter(const Graph< T > &g) : Graph< T >(g) {} private: vector< int > to; pair< T, int > dfs(int idx, int par) { pair< T, int > ret(0, idx); for(auto &e : g[idx]) { if(e.to == par) continue; auto cost = dfs(e.to, idx); cost.first += e.cost; if(ret < cost) { ret = cost; to[idx] = e.to; } } return ret; } }; int main() { FAST_IO auto ans = 0LL; int N; cin >> N; vector<int> u(N-1), v(N-1); vector<i64> w(N-1); for (int i = 0; i < N - 1; i ++) { cin >> u[i] >> v[i] >> w[i]; u[i] --; v[i] --; } Graph<i64> g(N); for (int i = 0; i < N - 1; i ++) { g.add_edge(u[i], v[i], w[i]); } TreeDiameter<i64> td(g); auto d = td.build(); cout << d << endl; }