結果

問題 No.3113 The farthest point
コンテスト
ユーザー stderr0r
提出日時 2025-04-19 18:07:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,113 bytes
コンパイル時間 1,751 ms
コンパイル使用メモリ 162,188 KB
実行使用メモリ 21,696 KB
最終ジャッジ日時 2025-04-19 18:07:10
合計ジャッジ時間 6,179 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region my_template
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using ti = tuple<int, int, int>;
using tl = tuple<ll, ll, ll>;
using vi = vector<int>;
using vpi = vector<pi>;
using vti = vector<ti>;
using vvi = vector<vi>;
using usi = unordered_set<int>;
using vl = vector<ll>;
using vpl = vector<pl>;
using vtl = vector<tl>;
using vvl = vector<vl>;
using usl = unordered_set<ll>;
 
#define range(i, l, r) for(int i = (int)(l); i < (int)(r); i++)
#define rrange(i, l, r) for(int i = (int)(r)-1; i >= (int)(l); i--)
#define rep(i, n) range(i, 0, n)
#define rrep(i, n) rrange(i, 0, n)
#define len(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sum(a) accumulate(all(a), 0)
#define it2idx(a, it) distance(a.begin(), it)
#define idx2it(a, idx) next(a.begin(), idx)
#define elif else if
 
namespace io {
    #ifdef LOCAL
    ofstream dout("./dmp.txt");
    #else
    ofstream dout("/dev/null");
    #endif
    template<typename T, typename U>
    istream &operator >> (istream &in, pair<T, U> &a){
        in >> a.first >> a.second;
        return in;
    }
    template<typename T>
    istream &operator >> (istream &in, vector<T> &a){
        for(T &x: a) in >> x;
        return in;
    }
    template<typename T, typename U>
    ostream &operator << (ostream &out, const pair<T, U> &a){
        out << a.first << " " << a.second;
        return out;
    }
    template<typename T>
    ostream &operator << (ostream &out, const vector<T> &a) {
        rep(i, len(a)) out << a[i] << (i == len(a)-1 ? "" : " ");
        return out;
    }
    template<typename T>
    ostream &operator << (ostream &out, const unordered_set<T> &a) {
        int i = 0;
        for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; }
        return out;
    }
    template<typename T>
    ostream &operator << (ostream &out, const set<T> &a) {
        int i = 0;
        for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; }
        return out;
    }
    template<typename T>
    ostream &operator << (ostream &out, const multiset<T> &a) {
        int i = 0;
        for (const T &x: a) { out << x << (i == len(a)-1 ? "" : " "); i++; }
        return out;
    }
    inline void print() { cout << "\n"; }
    template <typename T, typename ...U>
    inline void print(const T &t, const U &...u) {
        cout << t;
        if (sizeof...(u)) cout << " ";
        print(u...);
    }
    inline void dmp() { dout << endl; }
    template <typename T, typename ...U>
    inline void dmp(const T &t, const U &...u) {
        dout << t;
        if (sizeof...(u)) dout << " ";
        dmp(u...);
    }
}
using namespace io;
 
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
void solve();

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr int MOD = 1e9+7;
//constexpr int MOD = 998244353;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    solve();
    return 0;
}
#pragma endregion


// https://ei1333.github.io/library/graph/tree/tree-diameter.hpp

#line 2 "graph/tree/tree-diameter.hpp"

#line 2 "graph/graph-template.hpp"

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> >;
#line 4 "graph/tree/tree-diameter.hpp"

/**
 * @brief Tree-Diameter(木の直径)
 *
 */
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;
  }
};


void solve() {
    int N;
    cin >> N;
    TreeDiameter<ll> g(N);
    g.read(N-1, -1, true);
    cout << g.build() << endl;
}
0