結果

問題 No.2780 The Bottle Imp
コンテスト
ユーザー NakLon131
提出日時 2024-06-12 06:33:17
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 2,268 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 16,506 ms
コンパイル使用メモリ 378,540 KB
実行使用メモリ 33,280 KB
最終ジャッジ日時 2024-06-12 06:33:38
合計ジャッジ時間 18,364 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
fn main() {
    input!{
        n: usize,
    }

    // 有向辺と逆辺
    let mut uv = vec![Vec::new(); n];
    let mut ruv = vec![Vec::new(); n];
    for from in 1..=n {
        input!{
            m: usize,
        }
		if m == 0 { continue; }
		input!{
			a: [usize; m],
		}
		for to in a {
            uv[from-1].push(to-1);
            ruv[to-1].push(from-1);
        }
    }
    // -- 強連結成分分解 -- 
	// 有向辺DFSして帰りがけに頂点を記録
	fn dfs(spos: usize, uv: &Vec<Vec<usize>>, n: usize, used: &mut Vec<bool>, orders: &mut Vec<usize>){
		used[spos] = true;
		for &npos in &uv[spos] {
			if used[npos] { continue; }
			dfs(npos, uv, n, used, orders);
		}
		orders.push(spos);
	}
	let mut used = vec![false; n];
	let mut orders = Vec::new();
	for i in 0..n {
		if used[i] { continue; }
		dfs(i, &uv, n, &mut used, &mut orders);
	}
	// 記録した頂点と逆順に逆辺有向辺DFS
	fn rdfs(spos: usize, ruv: &Vec<Vec<usize>>, n: usize, used: &mut Vec<bool>, compo: &mut Vec<Vec<usize>>, cnt: usize) {
		used[spos] = true;
		compo[cnt].push(spos);
		for &npos in &ruv[spos] {
			if used[npos] { continue; }
			rdfs(npos, ruv, n, used, compo, cnt);
		}
	}
	let mut compo_cnt = 0;
	let mut used = vec![false; n];
	let mut compo = Vec::new();
	orders.reverse();
	for &i in &orders {
		if used[i] { continue; }
		compo.push(Vec::new());
		rdfs(i, &ruv, n, &mut used, &mut compo, compo_cnt);
		compo_cnt += 1;
	}
	// -- 強連結成分分解 -- 

	// 各頂点を連結成分のグループに割り当て
	let mut compo_group = vec![0; n];
	for i in 0..compo.len() {
		for &c in &compo[i] {
			compo_group[c] = i;
		}
	} 

	// 初めの連結成分が0でない場合は、No
	if compo_group[0] != 0 {
		println!("No");
		return;
	}

	// 連結成分を順番に辿る
	// 辿ることができない連結成分があったらNo
	for i in 0..compo.len()-1 {
		let mut f = false;
		// 各連結成分の頂点
		for &from in &compo[i] {
			// 各連結成分にある有向辺
			for &to in &uv[from] {
				// k->l について、連結成分が連番であればよい。
				if compo_group[from] + 1 == compo_group[to] { f = true; }
			}
		}
		if !f {
			println!("No");
			return;
		}
	}
	println!("Yes");	
}
0