結果
問題 |
No.3113 The farthest point
|
ユーザー |
|
提出日時 | 2025-04-19 10:45:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,752 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 198,684 KB |
実行使用メモリ | 22,708 KB |
最終ジャッジ日時 | 2025-04-19 10:45:46 |
合計ジャッジ時間 | 7,764 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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; const ll mx = 400400; VVP to(mx); // double sweep void getdist(ll cur, ll pa, ll dist, ll &maxInd, ll &maxDist) { if (dist > maxDist) { maxDist = dist; maxInd = cur; } for (auto [next, w] : to[cur]) { if (next == pa) continue; getdist(next, cur, dist + w, maxInd, maxDist); } } // 頂点a,b, 距離maxDist void doubleSweep(ll &a, ll &b, ll &maxDist) { a = 0, b = 0, maxDist = 0; getdist(0, -1, 0, a, maxDist); maxDist = 0; getdist(a, -1, 0, b, maxDist); } int main() { ll N; cin >> N; REP(i, N - 1) { ll a, b, c; cin >> a >> b >> c; a--, b--; to[a].emplace_back(b, c); to[b].emplace_back(a, c); } ll x, y, d; doubleSweep(x, y, d); COUT(d); }