結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー elphe
提出日時 2025-11-15 09:33:03
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 48 ms / 2,000 ms
コード長 2,286 bytes
コンパイル時間 11,587 ms
コンパイル使用メモリ 400,252 KB
実行使用メモリ 18,348 KB
最終ジャッジ日時 2025-11-15 09:33:20
合計ジャッジ時間 15,503 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{fastout, input};
use std::collections::VecDeque;

#[fastout]
fn main() {
    input! {
        n: usize,
        edges: [(u32, u32)],
        telescopes: [(u32, u32)],
    }

    let next_of = prepare_graph(n, edges);
    let is_reachable = prepare_telescopes(n, &next_of, telescopes);
    println!("{}", output(solve(n, next_of, is_reachable)));
}

fn prepare_graph(n: usize, edges: Vec<(u32, u32)>) -> Vec<Vec<u32>> {
    let mut next_of = vec![Vec::<u32>::with_capacity(100); n + 1];
    for (u, v) in edges {
        next_of[u as usize].push(v);
        next_of[v as usize].push(u);
    }
    next_of
}

fn prepare_telescopes(n: usize, next_of: &Vec<Vec<u32>>, telescopes: Vec<(u32, u32)>) -> Vec<bool> {
    let mut event_list = vec![Vec::<u32>::with_capacity(10000); 1001];
    for (j, k) in telescopes {
        event_list[(1000 - k) as usize].push(j);
    }

    let mut is_reachable = vec![true; n + 1];
    let mut cur_q = Vec::new();
    let mut next_q = Vec::new();
    for events in event_list {
        (cur_q, next_q) = (next_q, cur_q);
        while let Some(cur) = cur_q.pop() {
            for next in next_of[cur as usize].iter() {
                if is_reachable[*next as usize] {
                    is_reachable[*next as usize] = false;
                    next_q.push(*next);
                }
            }
        }
        for addition in events {
            if is_reachable[addition as usize] {
                is_reachable[addition as usize] = false;
                next_q.push(addition);
            }
        }
    }
    is_reachable
}

fn solve(n: usize, next_of: Vec<Vec<u32>>, is_reachable: Vec<bool>) -> u32 {
    let mut dist = vec![u32::MAX; n + 1];
    let mut q = VecDeque::new();
    if is_reachable[1] {
        dist[1] = 0;
        q.push_back(1);
    }

    while let Some(cur) = q.pop_front() {
        for next in next_of[cur as usize].iter() {
            if is_reachable[*next as usize] && dist[*next as usize] == u32::MAX {
                dist[*next as usize] = dist[cur as usize] + 1;
                q.push_back(*next);
            }
        }
    }
    dist[n]
}

fn output(ans: u32) -> String {
    match ans {
        u32::MAX => String::from("No"),
        dist => String::from("Yes\n") + &dist.to_string(),
    }
}
0