結果

問題 No.3326 岩井星人の帰星
コンテスト
ユーザー elphe
提出日時 2025-11-15 09:08:18
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 2,642 bytes
コンパイル時間 26,351 ms
コンパイル使用メモリ 400,368 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2025-11-15 09:08:50
合計ジャッジ時間 17,828 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 deg_of = vec![0u32; n + 1];
	for (u, v) in edges.iter() {
		deg_of[*u as usize] += 1;
		deg_of[*v as usize] += 1;
	}

    let mut next_of = Vec::new();
	for deg in deg_of {
		next_of.push(Vec::with_capacity(deg as usize));
	}
    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 count_of = [0u32; 1001];
	for (_, k) in telescopes.iter() {
		count_of[(1000 - *k) as usize] += 1;
	}
	
    let mut event_list = Vec::new();
	for count in count_of {
		event_list.push(Vec::with_capacity(count as usize));
	}
    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 = VecDeque::new();
    let mut next_q = VecDeque::new();
    for events in event_list {
        (cur_q, next_q) = (next_q, cur_q);
        while let Some(cur) = cur_q.pop_front() {
            for next in next_of[cur as usize].iter() {
                if is_reachable[*next as usize] {
                    is_reachable[*next as usize] = false;
                    next_q.push_back(*next);
                }
            }
        }
        for addition in events {
            if is_reachable[addition as usize] {
                is_reachable[addition as usize] = false;
                next_q.push_back(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