結果
問題 |
No.3113 The farthest point
|
ユーザー |
|
提出日時 | 2025-04-15 15:36:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 328 ms / 2,000 ms |
コード長 | 1,036 bytes |
コンパイル時間 | 3,553 ms |
コンパイル使用メモリ | 294,992 KB |
実行使用メモリ | 33,256 KB |
最終ジャッジ日時 | 2025-04-15 15:36:34 |
合計ジャッジ時間 | 9,772 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; bool chmax(ll &a,ll b){ if(a<b){ a=b; return 1; } return 0; } int main(){ int N; cin>>N; using edge = pair<int,ll>; vector G(N,vector<edge>()); for(int i=0;i<N-1;i++){ int U,V; ll C; cin>>U>>V>>C; --U,--V; G[U].push_back(edge{V,C}); G[V].push_back(edge{U,C}); } vector d(N,-1),p(N,-1); vector pw(N,0ll); vector child(N,vector<ll>()); stack<int>dfs; dfs.push(0); ll ans=0; while(dfs.size()){ int v=dfs.top(); dfs.pop(); for(int &i=++d[v];i<G[v].size();i++){ auto [v2,w]=G[v][i]; if(v2!=p[v]){ dfs.push(v); dfs.push(v2); p[v2]=v; pw[v2]=w; break; } } if(d[v]==G[v].size()){ auto &c=child[v]; c.push_back(0); sort(c.begin(),c.end(),greater<ll>()); if(c.size()>=2){ chmax(ans,c[0]+c[1]); } if(p[v]!=-1){ child[p[v]].push_back(c[0]+pw[v]); } } } cout<<ans<<'\n'; }