結果

問題 No.2780 The Bottle Imp
ユーザー NakLon131NakLon131
提出日時 2024-06-12 06:33:17
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 2,268 bytes
コンパイル時間 16,506 ms
コンパイル使用メモリ 378,540 KB
実行使用メモリ 33,280 KB
最終ジャッジ日時 2024-06-12 06:33:38
合計ジャッジ時間 18,364 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 36 ms
12,160 KB
testcase_08 AC 38 ms
12,160 KB
testcase_09 AC 36 ms
12,160 KB
testcase_10 AC 35 ms
12,160 KB
testcase_11 AC 34 ms
12,160 KB
testcase_12 AC 90 ms
22,144 KB
testcase_13 AC 69 ms
22,016 KB
testcase_14 AC 17 ms
6,400 KB
testcase_15 AC 16 ms
6,528 KB
testcase_16 AC 17 ms
6,400 KB
testcase_17 AC 17 ms
6,400 KB
testcase_18 AC 17 ms
6,400 KB
testcase_19 AC 16 ms
6,400 KB
testcase_20 AC 16 ms
6,400 KB
testcase_21 AC 16 ms
6,528 KB
testcase_22 AC 12 ms
5,632 KB
testcase_23 AC 15 ms
6,144 KB
testcase_24 AC 27 ms
10,496 KB
testcase_25 AC 51 ms
16,512 KB
testcase_26 AC 23 ms
8,832 KB
testcase_27 AC 17 ms
9,440 KB
testcase_28 AC 17 ms
9,564 KB
testcase_29 AC 23 ms
12,032 KB
testcase_30 AC 16 ms
9,728 KB
testcase_31 AC 36 ms
18,048 KB
testcase_32 AC 6 ms
5,376 KB
testcase_33 AC 47 ms
27,264 KB
testcase_34 AC 57 ms
33,280 KB
testcase_35 AC 6 ms
5,376 KB
testcase_36 AC 1 ms
5,376 KB
testcase_37 AC 1 ms
5,376 KB
testcase_38 AC 6 ms
5,376 KB
testcase_39 AC 29 ms
17,312 KB
testcase_40 AC 31 ms
17,180 KB
testcase_41 AC 31 ms
17,304 KB
testcase_42 AC 1 ms
5,376 KB
testcase_43 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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