結果
| 問題 |
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 |
ソースコード
#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;
}