結果
| 問題 |
No.3113 The farthest point
|
| ユーザー |
 かえる☔
|
| 提出日時 | 2025-04-19 11:04:15 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,490 bytes |
| コンパイル時間 | 13,108 ms |
| コンパイル使用メモリ | 400,968 KB |
| 実行使用メモリ | 39,376 KB |
| 最終ジャッジ日時 | 2025-04-19 11:04:33 |
| 合計ジャッジ時間 | 17,137 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 WA * 5 |
コンパイルメッセージ
warning: unused import: `marker::Chars as chars`
--> src/main.rs:1:49
|
1 | use proconio::{input, marker::Usize1 as usize1, marker::Chars as chars};
| ^^^^^^^^^^^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
warning: unused imports: `BTreeMap`, `BTreeSet`, `HashMap`, `HashSet`, `VecDeque as Deque`, `default::Default`, `io::Write`, and `mem::swap`
--> src/main.rs:2:25
|
2 | use std::{collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque as Deque}, default::Default, io::Write, mem::swap};
| ^^^^^^^^ ^^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^ ^^^^^^^^^ ^^^^^^^^^
warning: unused macro definition: `chmin`
--> src/main.rs:12:14
|
12 | macro_rules! chmin {
| ^^^^^
|
= note: `#[warn(unused_macros)]` on by default
warning: function `yn` is never used
--> src/main.rs:21:4
|
21 | fn yn(x: bool) {
| ^^
|
= note: `#[warn(dead_code)]` on by default
warning: function `extend_euclid` is never used
--> src/main.rs:29:4
|
29 | fn extend_euclid(a: i64, b: i64) -> Result<(i64, i64), i64> {
| ^^^^^^^^^^^^^
warning: struct `DisjointSetUnion` is never constructed
--> src/main.rs:51:8
|
51 | struct DisjointSetUnion {
| ^^^^^^^^^^^^^^^^
warning: associated items `new`, `root`, `size`, `union`, and `connections` are never used
--> src/main.rs:57:8
|
56 | impl DisjointSetUnion {
| --------------------- associated items in this implementation
57 | fn new(N: usize) -> Self {
| ^^^
...
63 | fn root(&self, x: usize) -> usize {
| ^^^^
...
70 | fn size(&self, x: usize) -> usize {
| ^^^^
...
73 | fn union(&mut self, a: usize, b: usize) -> bool {
| ^^^^^
...
91 | fn connections(&self) -> Vec<usize> {
| ^^^^^^^^^^^
warning: struct `SegTree` is never constructed
--> src/main.rs:102:8
|
102 | struct SegTree<T: Co
ソースコード
use proconio::{input, marker::Usize1 as usize1, marker::Chars as chars};
use std::{collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque as Deque}, default::Default, io::Write, mem::swap};
macro_rules! chmax {
($target:expr, $value:expr) => {
if $target < $value {
$target = $value;
true
} else {false}
};
}
macro_rules! chmin {
($target:expr, $value:expr) => {
if $target > $value {
$target = $value;
true
} else {false}
};
}
fn yn(x: bool) {
if x {
println!("Yes")
} else {
println!("No")
}
}
fn extend_euclid(a: i64, b: i64) -> Result<(i64, i64), i64> {
/*
ax+by=1 を満たすOk((x, y))を返す。存在しなければErr(gcd(a, b))を返す。
*/
fn inner(a: i64, b: i64, ae: (i64, i64), be: (i64, i64)) -> Result<(i64, i64), i64> {
if b == 0 {
if a == 1 {
return Ok(ae);
} else {
return Err(a);
}
}
let mut new_be = (0, 0);
new_be.0 = ae.0 - a / b * be.0;
new_be.1 = ae.1 - a / b * be.1;
inner(b, a%b, be, new_be)
}
inner(a, b, (1, 0), (0, 1))
}
#[derive(Debug)]
struct DisjointSetUnion {
parents: Vec<usize>,
children: Vec<Vec<usize>>,
sizes: Vec<usize>,
}
impl DisjointSetUnion {
fn new(N: usize) -> Self {
let parents = (0..N).collect();
let children = vec![vec![]; N];
let sizes = vec![1; N];
Self { parents, children, sizes }
}
fn root(&self, x: usize) -> usize {
if self.parents[x] == x {
x
} else {
self.root(self.parents[x])
}
}
fn size(&self, x: usize) -> usize {
self.sizes[self.root(x)]
}
fn union(&mut self, a: usize, b: usize) -> bool {
let (a, b) = (self.root(a), self.root(b));
if a==b {
return false;
}
if self.size(a) > self.size(b) {
self.parents[b] = a;
self.children[a].push(b);
self.sizes[a] += self.sizes[b];
self.sizes[b] = 0;
} else {
self.parents[a] = b;
self.children[b].push(a);
self.sizes[b] += self.sizes[a];
self.sizes[a] = 0;
}
true
}
fn connections(&self) -> Vec<usize> {
let mut res = Vec::new();
for i in 0..self.parents.len() {
if self.root(i) == i {
res.push(i)
}
}
res
}
}
struct SegTree<T: Copy> {
size: usize,
dat: Vec<T>,
update_func: Box<dyn Fn(T, T) -> T>,
identity: T,
}
impl<T: Copy> SegTree<T> {
fn new(size: usize, update_func: impl Fn(T, T) -> T + 'static, identity: T) -> Self {
let size = size.next_power_of_two();
let dat = vec![identity.clone(); size*2-1];
Self {
size, dat, update_func: Box::new(update_func), identity,
}
}
fn update(&mut self, mut i: usize, x: T) {
i += self.size-1;
self.dat[i] = x;
while i > 0 {
i = (i-1)/2;
self.dat[i] = (self.update_func)(self.dat[i*2+1], self.dat[i*2+2]);
}
}
fn query(&self, a: usize, b: usize) -> T {
self.query_sub(a, b, 0, 0, self.size)
}
fn query_sub(&self, a: usize, b: usize, k: usize, l: usize, r: usize) -> T {
if r <= a || b <= l {
self.identity
} else if a <= l && r <= b {
self.dat[k]
} else {
(self.update_func)(self.query_sub(a, b, k*2+1, l, (l+r)/2), self.query_sub(a, b, k*2+2, (l+r)/2, r))
}
}
}
impl SegTree<i64> {
fn new_rminq(size: usize) -> Self {
Self::new(size, i64::min, std::i64::MAX)
}
fn new_rmaxq(size: usize) -> Self {
Self::new(size, i64::max, std::i64::MIN)
}
fn new_rsq(size: usize) -> Self {
Self::new(size, |a, b| a+b, 0)
}
}
impl SegTree<usize> {
fn new_rminq(size: usize) -> Self {
Self::new(size, usize::min, std::usize::MAX)
}
fn new_rmaxq(size: usize) -> Self {
Self::new(size, usize::max, std::usize::MIN)
}
fn new_rsq(size: usize) -> Self {
Self::new(size, |a, b| a+b, 0)
}
}
fn around(i: usize, j: usize, H: usize, W: usize) -> Vec<(usize, usize)> {
let mut res = vec![];
if i!=0 {
res.push((i-1, j));
}
if j!=0 {
res.push((i, j-1));
}
if i!=H-1 {
res.push((i+1, j));
}
if j!=W-1 {
res.push((i, j+1))
}
res
}
fn to_index(i: usize, j: usize, W: usize) -> usize {
i*W+j
}
fn lowerchar2code(c: char) -> usize {
c as usize - 'a' as usize
}
type ModType = usize;
static MOD: ModType = 998244353;
fn pow(base: ModType, power: ModType) -> ModType {
if power == 0 {
1
} else if power == 1 {
base % MOD
} else {
if power % 2 == 0 {
pow(base, power/2).pow(2) % MOD
} else {
let tmp = pow(base, power/2).pow(2) % MOD;
tmp * base % MOD
}
}
}
fn recip(x: ModType) -> ModType {
pow(x, MOD-2)
}
fn main() {
input! {
N: usize,
uvw: [(usize1, usize1, i64); N-1],
}
let mut children = vec![vec![]; N];
let mut edges = vec![vec![]; N];
for (u, v, w) in uvw {
edges[u].push((v, w));
edges[v].push((u, w));
}
let mut stack = vec![0];
let mut reached = vec![false; N];
reached[0] = true;
while let Some(v) = stack.pop() {
for (u, w) in edges[v].clone() {
if reached[u] {
continue;
}
reached[u] = true;
children[v].push((u, w));
stack.push(u);
}
}
let mut solver = Solver{children, ans:0};
solver.solve(0);
println!("{}", solver.ans);
}
struct Solver {
children: Vec<Vec<(usize, i64)>>,
ans: i64,
}
impl Solver {
fn solve(&mut self, v: usize) -> i64 {
let mut children_ans = vec![];
for (u, w) in self.children[v].clone() {
children_ans.push(w+self.solve(u));
}
children_ans.sort(); children_ans.reverse();
match children_ans[..] {
[a, b, ..] => {
chmax!(self.ans, a+b);
a
},
[a] => {
chmax!(self.ans, a);
a
},
[] => 0
}
}
}