#1078512 (C++23) No.3113 The farthest point

提出ソース
結果

問題	No.3113 The farthest point
ユーザー	eiya5498513
提出日時	2025-04-20 19:44:12
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	217 ms / 2,000 ms
コード長	10,152 bytes
コンパイル時間	3,821 ms
コンパイル使用メモリ	215,756 KB
実行使用メモリ	28,248 KB
最終ジャッジ日時	2025-04-20 19:44:21
合計ジャッジ時間	8,696 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 33
権限があれば一括ダウンロードができます
ソースコード

raw source code
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 26450 )
#pragma warning( disable : 26451 )
#pragma warning( disable : 26498 )
#pragma warning( disable : 4459 )
#endif
#include <atcoder/all>
#ifdef _MSC_VER
#pragma warning( pop )
#endif

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


constexpr int32_t MAX_N = 600000;//頂点数
constexpr int32_t MAX_LOGN = 30;//log2頂点数
struct edge{
	int to;
	int64_t w;
};
std::vector<edge> graph[MAX_N];//木
namespace nLCA
{
	int root; // 根ノードの番号
	int parent[MAX_LOGN][MAX_N]; // 親を2^k回辿って到達する頂点(根を通り過ぎる場合は-1とする)
	int depth[MAX_N]; // 根からの深さ
	int64_t dist[MAX_N]; // 根からの遠さ
	void dfs(int v, int p, int d, int64_t w) {
		parent[0][v] = p;
		depth[v] = d;
		dist[v] = w;
		for (int i = 0; i < graph[v].size(); i++) {
			if (graph[v][i].to != p) dfs(graph[v][i].to, v, d + 1, w + graph[v][i].w);
		}
	}
	// 初期化
	void init(int V) {
		// parent[0]とdepthを初期化する
		dfs(root, -1, 0, 0);
		// parentを初期化する
		for (int k = 0; k + 1 < MAX_LOGN; k++) {
			for (int v = 0; v < V; v++) {
				if (parent[k][v] < 0) parent[k + 1][v] = -1;
				else parent[k + 1][v] = parent[k][parent[k][v]];
			}
		}
	}
	// uとvのLCAを求める
	int glca(int u, int v) {
		// uとvの深さが同じになるまで親を辿る
		if (depth[u] > depth[v]) std::swap(u, v);
		for (int k = 0; k < MAX_LOGN; k++) {
			if ((depth[v] - depth[u]) >> k & 1) {
				v = parent[k][v];
			}
		}
		if (u == v) return u;
		// 二分探索でLCAを求める
		for (int k = MAX_LOGN - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v]) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}


	std::pair<int64_t, int64_t>  dfs2(int v) {
		int64_t max1 = 0;
		int64_t max2 = 0;
		int64_t max_res = 0;
		for (int i = 0; i < graph[v].size(); i++) {
			if (graph[v][i].to != parent[0][v]) {
				auto new_res = dfs2(graph[v][i].to);
				max_res = std::max(max_res, new_res.second);
				auto new_d = new_res.first + graph[v][i].w;
				if (new_d >= max1) {
					max2 = max1;
					max1 = new_d;
				}
				else if (new_d >= max2) {
					max2 = new_d;
				}
			}
		}

		max_res = std::max(max_res, max1 + max2);
		return { max1 ,max_res };
	}
}
int32_t N;
void input_tree()
{
	in >> N;
	for (int32_t i = 0; i < N - 1; ++i)
	{
		int a, b;
		int64_t w;
		in >> a >> b >> w; --a; --b;
		graph[a].push_back({ b, w });
		graph[b].push_back({ a, w });
	}
}


int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	input_tree();
	nLCA::init(0);
	auto res = nLCA::dfs2(0);
	out << res.second << endl;

	return 0;
}
#endif



#if 0
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>
#ifdef _MSC_VER
#pragma warning( push )
#pragma warning( disable : 26450 )
#pragma warning( disable : 26451 )
#pragma warning( disable : 26498 )
#pragma warning( disable : 4459 )
#endif
#include <atcoder/all>
#ifdef _MSC_VER
#pragma warning( pop )
#endif

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

template<typename Arithmetic, typename Integral>
std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>
ipow(Arithmetic bace, Integral n)
{
	//繰り返し二条法
	auto res = (Arithmetic)(1);
	while (n > 0) {
		if (n & 1) res *= bace;
		bace *= bace;
		n >>= 1;
	}
	return res;
}
constexpr bool is_prime(uint32_t N)
{
	if (N <= 1) {
		return false;
	}
	for (size_t i = 2; i * i <= N; ++i)
	{
		if (N % i == 0) {
			return false;
		}
	}
	return true;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 998244353>
class mint_base
{
public:
	static constexpr auto MOD = MOD_;
	static_assert(!(MOD <= 2), "MOD cannot be below 2.");
	static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
	static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
	constexpr mint_base<MOD> operator+(const mint_base<MOD>& other)const noexcept
	{
		auto v = *this;
		return v += other;
	}
	constexpr mint_base<MOD> operator-(const mint_base<MOD>& other)const noexcept
	{
		auto v = *this;
		return v -= other;
	}
	constexpr mint_base<MOD> operator*(const mint_base<MOD>& other)const noexcept
	{
		auto v = *this;
		return v *= other;
	}
	constexpr auto operator/(const mint_base<MOD>& other)const noexcept
	{
		auto v = *this;
		return v /= other;
	}
	constexpr mint_base<MOD>& operator+=(const mint_base<MOD>& other) noexcept
	{
		a += other.a;
		if (MOD <= a) { a -= MOD; };
		return *this;
	}
	constexpr mint_base<MOD>& operator-=(const mint_base<MOD>& other) noexcept
	{
		if (a >= other.a) {
			a -= other.a;
		}
		else {
			a = (a + MOD) - other.a;
		}
		return *this;
	}
	constexpr mint_base<MOD>& operator*=(const mint_base<MOD>& other) noexcept
	{
#if 1
		a *= other.a;
		a %= MOD;
#else
		//MOD <= (MAXUINT64 / 2)条件下
		uint64_t b = other.a, v = 0;
		while (b > 0) {
			if (b & 1) {
				v += a;
				if (v >= MOD)v -= MOD;
			}
			a += a;
			if (MOD <= a)a -= MOD;
			b >>= 1;
		}
		a = v;
#endif
		return *this;
	}
	constexpr mint_base<MOD>& operator/=(const mint_base<MOD>& other) noexcept
	{
		return *this *= ~other;
	}
	constexpr mint_base<MOD> operator+()const noexcept { return *this; }
	constexpr mint_base<MOD> operator-()const noexcept
	{
		return{ MOD - a, mod_value_tag{} };
	}
	constexpr mint_base<MOD>& operator++() noexcept
	{
		if (MOD <= ++a) { a = 0; };
		return *this;
	}
	constexpr mint_base<MOD>& operator--() noexcept
	{
		if (a <= 0) { a = MOD; };
		--a;
		return *this;
	}
	constexpr mint_base<MOD> operator++(int) noexcept
	{
		auto tmp = *this;
		++*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator--(int) noexcept
	{
		auto tmp = *this;
		--*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator~()const noexcept
	{
		return ipow(*this, e_phi - 1);
	}
	constexpr mint_base<MOD>& operator=(const mint_base<MOD>& other) noexcept
	{
		a = other.a;
		return *this;
	}
	constexpr explicit operator uint64_t()const noexcept
	{
		return a;
	}
	constexpr explicit operator unsigned()const noexcept
	{
		return (unsigned)a;
	}
	static constexpr uint64_t getmod() noexcept
	{
		return MOD;
	}
	constexpr mint_base(uint64_t a_) noexcept :a(a_% MOD) {}
	constexpr mint_base()noexcept : a(0) {}
	struct mod_value_tag {};
	constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
	static constexpr uint64_t get_e_phi()noexcept {
		//オイラー値の導出
		uint64_t temp = MOD;
		uint64_t m_ = MOD;
		for (uint64_t i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				temp = temp / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)temp = temp / m_ * (m_ - 1);
		return temp;
	}
	static constexpr uint64_t e_phi = get_e_phi();//オイラー値
	uint64_t a;
};
//mint_base型用の累乗関数
template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept
{
	mint_base<MOD> res = 1;
	while (n > 0)
	{
		if (n & 1)res *= x;
		x *= x;
		n >>= 1;
	}
	return res;
}
//mint_baseの階乗計算
//O(x)時間が必要のため、fact_set関数を推奨する。
template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept
{
	mint_base<MOD> res(1);
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
	}
	return res;
}
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(x)時間が必要
template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1))
{
	mint_base<MOD> res(1);
	std::vector<mint_base<MOD>> set((uint64_t)(x)+1);
	set[0] = 1;
	for (uint64_t i = 1; i <= (uint64_t)x; ++i)
	{
		res *= i;
		set[i] = res;
	}
	return res;
}
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
	os << (uint64_t)i;
	return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
	uint64_t tmp;
	is >> tmp;
	i = tmp;
	return is;
}
typedef mint_base<> mint;
namespace mint_literal {
	constexpr mint operator""_mi(unsigned long long x)noexcept {
		return mint(x);
	}
}
using namespace mint_literal;
int64_t A[300000];
mint mn[300000];
int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	int64_t N;
	mint M;
	in >> N >> M;
	for (int i = 0; i < N; i++)
	{
		in >> A[i];
	}

	std::sort(A, A + N);

	mint over = 0;
	mn[0] = 1;
	for (size_t i = 1; i < 300000; i++) {
		mn[i] = mn[i - 1] * M;
	}

	mint swapsum = 0;
	mint sum = 0;
	for (int i = N - 1; i >= 0; i--)
	{
		if (i != N - 1) {
			over = mint(N - i - 1) * mint(A[i + 1] - A[i]);
		}
		sum += (M - A[i]) * mn[N-1];
		auto swap = mint(A[i]) * over * mn[N-2];
		swap -= swapsum / M * mint(A[i]);
		swapsum += swap;
		sum += swap;
	}
	out << sum << endl;


	return 0;


}
#endif
yukicoder

結果

ソースコード
