結果
問題 |
No.3113 The farthest point
|
ユーザー |
|
提出日時 | 2025-04-19 10:55:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,026 bytes |
コンパイル時間 | 2,205 ms |
コンパイル使用メモリ | 197,736 KB |
実行使用メモリ | 18,004 KB |
最終ジャッジ日時 | 2025-04-19 10:56:04 |
合計ジャッジ時間 | 8,464 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 WA * 13 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; // -------------------------------------------------------- template <class T> bool chmax(T &a, const T b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T &a, const T b) { if (b < a) { a = b; return 1; } return 0; } #define FOR(i, l, r) for (ll i = (l); i < (r); ++i) #define RFOR(i, l, r) for (ll i = (r) - 1; (l) <= i; --i) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) #define ALL(c) (c).begin(), (c).end() #define RALL(c) (c).rbegin(), (c).rend() #define SORT(c) sort(ALL(c)) #define RSORT(c) sort(RALL(c)) #define MIN(c) *min_element(ALL(c)) #define MAX(c) *max_element(ALL(c)) #define SUM(c) accumulate(ALL(c), 0LL) #define BITCNT(c) __builtin_popcountll(c) #define SZ(c) ((int)(c).size()) #define COUT(c) cout << (c) << '\n' #define debug(x) cerr << #x << " = " << (x) << '\n'; using P = pair<ll, ll>; using VP = vector<P>; using VVP = vector<VP>; using VS = vector<string>; using VI = vector<int>; using VVI = vector<VI>; using VLL = vector<ll>; using VVLL = vector<VLL>; using VB = vector<bool>; using VVB = vector<VB>; using VD = vector<double>; using VVD = vector<VD>; static const double EPS = 1e-10; static const double PI = acos(-1.0); template <typename T> void arrPrint(vector<T> arr) { for (auto v : arr) cout << v << " "; cout << '\n'; } template <typename T> void arrPrint2Dim(vector<vector<T>> arr) { for (auto a : arr) arrPrint(a); } template <typename T, typename T2> void arrPrintPair(vector<pair<T, T2>> arr) { for (auto v : arr) cout << "{" << v.first << "," << v.second << "}, "; cout << '\n'; } const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } // static const int INF = (1 << 30) - 1; // 1073741824 - 1 static const ll INF = (1LL << 62) - 1; // 4611686018427387904 - 1 // static const ll MOD = 1000000007; static const ll MOD = 998244353; template <typename T> struct Edge { ll to; T cost; }; using Graph = vector<vector<Edge<long long>>>; // cost の型を long long に指定 /* tree_diamiter : dfs を用いて重み付き木 T の直径を求める 計算量: O(N) */ template <typename T> pair<T, int> dfs(const Graph &G, int u, int par) { // 最遠点間距離と最遠点を求める pair<T, int> ret = make_pair((T)0, u); for (auto e : G[u]) { if (e.to == par) continue; auto next = dfs<T>(G, e.to, u); next.first += e.cost; ret = max(ret, next); } return ret; } template <typename T> T tree_diamiter(const Graph &G) { pair<T, int> p = dfs<T>(G, 0, -1); pair<T, int> q = dfs<T>(G, p.second, -1); return q.first; } int main() { ll N; cin >> N; Graph graph(N); REP(i, N - 1) { ll a, b, c; cin >> a >> b >> c; a--, b--; graph[a].push_back({b, c}); graph[b].push_back({a, c}); } ll ans = tree_diamiter<ll>(graph); COUT(ans); }