結果

問題 No.3113 The farthest point
コンテスト
ユーザー sig_256
提出日時 2025-04-19 15:38:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 988 ms / 2,000 ms
コード長 1,142 bytes
コンパイル時間 4,887 ms
コンパイル使用メモリ 109,576 KB
実行使用メモリ 40,288 KB
最終ジャッジ日時 2025-04-19 15:38:55
合計ジャッジ時間 19,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

std::vector<std::vector<std::pair<int, int>>> T;
std::map<std::pair<int, int>, long long> memo;

long long dfs(int src, int me){
	if(memo.count({src, me}) == 0){
		long long w = 0, w_0 = 0;
		for(const auto & p : T[me]){
			if(p.first == src){
				w_0 = p.second;
				continue;
			}
			w = std::max(w, dfs(me, p.first));
		}
		w = std::max(w + w_0, 0LL);
		memo.emplace(std::make_pair(src, me), w);
	}
	return memo.at({src, me});
}

int main(){
	int N, u, v, w;
	std::cin >> N;
	T.resize(N);
	for(int n = 1; n < N; ++n){
		std::cin >> u >> v >> w;
		u -= 1, v -= 1;
		T[u].emplace_back(v, w);
		T[v].emplace_back(u, w);
	}
	long long ans = 0;
	for(int n = 0; n < N; ++n){
		std::vector<long long> temp;
		for(const auto & p : T[n]){
			temp.push_back(dfs(n, p.first));
		}
		if(temp.size() == 1){
			ans = std::max(ans, temp[0]);
		}
		else if(temp.size() > 1){
			std::nth_element(temp.begin(), temp.begin() + 2, temp.end());
			temp[1] = std::max(temp[1], 0LL);
			ans = std::max(ans, temp[0] + temp[1]);
		}
	}
	std::cout << ans << std::endl;
}
0