#831561 (Rust) No.1254 補強への架け橋

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	phspls
提出日時	2023-01-08 15:26:25
言語	Rust (1.77.0)
結果	AC
実行時間	78 ms / 2,000 ms
コード長	2,143 bytes
コンパイル時間	1,550 ms
コンパイル使用メモリ	155,592 KB
実行使用メモリ	28,988 KB
最終ジャッジ日時	2023-08-22 01:38:14
合計ジャッジ時間	14,208 ms
ジャッジサーバーID （参考情報）	judge15 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	1 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,376 KB
testcase_09	AC	1 ms 4,380 KB
testcase_10	AC	0 ms 4,380 KB
testcase_11	AC	1 ms 4,380 KB
testcase_12	AC	1 ms 4,376 KB
testcase_13	AC	1 ms 4,376 KB
testcase_14	AC	1 ms 4,376 KB
testcase_15	AC	1 ms 4,376 KB
testcase_16	AC	1 ms 4,376 KB
testcase_17	AC	1 ms 4,376 KB
testcase_18	AC	1 ms 4,380 KB
testcase_19	AC	1 ms 4,376 KB
testcase_20	AC	1 ms 4,380 KB
testcase_21	AC	1 ms 4,380 KB
testcase_22	AC	1 ms 4,380 KB
testcase_23	AC	1 ms 4,376 KB
testcase_24	AC	1 ms 4,376 KB
testcase_25	AC	1 ms 4,376 KB
testcase_26	AC	1 ms 4,376 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	1 ms 4,380 KB
testcase_29	AC	1 ms 4,376 KB
testcase_30	AC	1 ms 4,376 KB
testcase_31	AC	1 ms 4,376 KB
testcase_32	AC	1 ms 4,380 KB
testcase_33	AC	1 ms 4,380 KB
testcase_34	AC	1 ms 4,380 KB
testcase_35	AC	1 ms 4,380 KB
testcase_36	AC	1 ms 4,380 KB
testcase_37	AC	1 ms 4,376 KB
testcase_38	AC	1 ms 4,376 KB
testcase_39	AC	1 ms 4,376 KB
testcase_40	AC	1 ms 4,376 KB
testcase_41	AC	1 ms 4,380 KB
testcase_42	AC	1 ms 4,380 KB
testcase_43	AC	1 ms 4,380 KB
testcase_44	AC	1 ms 4,376 KB
testcase_45	AC	1 ms 4,380 KB
testcase_46	AC	1 ms 4,376 KB
testcase_47	AC	1 ms 4,380 KB
testcase_48	AC	1 ms 4,380 KB
testcase_49	AC	1 ms 4,376 KB
testcase_50	AC	1 ms 4,376 KB
testcase_51	AC	1 ms 4,380 KB
testcase_52	AC	1 ms 4,376 KB
testcase_53	AC	1 ms 4,380 KB
testcase_54	AC	1 ms 4,376 KB
testcase_55	AC	1 ms 4,376 KB
testcase_56	AC	1 ms 4,376 KB
testcase_57	AC	1 ms 4,380 KB
testcase_58	AC	1 ms 4,376 KB
testcase_59	AC	1 ms 4,376 KB
testcase_60	AC	1 ms 4,380 KB
testcase_61	AC	1 ms 4,376 KB
testcase_62	AC	1 ms 4,376 KB
testcase_63	AC	5 ms 4,376 KB
testcase_64	AC	2 ms 4,380 KB
testcase_65	AC	4 ms 4,376 KB
testcase_66	AC	3 ms 4,376 KB
testcase_67	AC	1 ms 4,376 KB
testcase_68	AC	3 ms 4,376 KB
testcase_69	AC	4 ms 4,376 KB
testcase_70	AC	2 ms 4,376 KB
testcase_71	AC	2 ms 4,376 KB
testcase_72	AC	4 ms 4,376 KB
testcase_73	AC	2 ms 4,380 KB
testcase_74	AC	4 ms 4,380 KB
testcase_75	AC	3 ms 4,376 KB
testcase_76	AC	1 ms 4,380 KB
testcase_77	AC	3 ms 4,376 KB
testcase_78	AC	5 ms 4,376 KB
testcase_79	AC	4 ms 4,380 KB
testcase_80	AC	4 ms 4,376 KB
testcase_81	AC	4 ms 4,376 KB
testcase_82	AC	4 ms 4,376 KB
testcase_83	AC	50 ms 12,416 KB
testcase_84	AC	44 ms 12,224 KB
testcase_85	AC	25 ms 8,516 KB
testcase_86	AC	37 ms 10,836 KB
testcase_87	AC	40 ms 11,696 KB
testcase_88	AC	7 ms 4,376 KB
testcase_89	AC	46 ms 12,484 KB
testcase_90	AC	28 ms 8,804 KB
testcase_91	AC	21 ms 7,480 KB
testcase_92	AC	11 ms 4,828 KB
testcase_93	AC	36 ms 10,360 KB
testcase_94	AC	34 ms 9,560 KB
testcase_95	AC	34 ms 9,600 KB
testcase_96	AC	42 ms 11,960 KB
testcase_97	AC	18 ms 6,420 KB
testcase_98	AC	44 ms 11,972 KB
testcase_99	AC	25 ms 8,252 KB
testcase_100	AC	44 ms 12,696 KB
testcase_101	AC	10 ms 4,572 KB
testcase_102	AC	6 ms 4,380 KB
testcase_103	AC	11 ms 4,828 KB
testcase_104	AC	15 ms 5,896 KB
testcase_105	AC	36 ms 10,320 KB
testcase_106	AC	20 ms 6,964 KB
testcase_107	AC	50 ms 12,508 KB
testcase_108	AC	44 ms 12,224 KB
testcase_109	AC	36 ms 10,388 KB
testcase_110	AC	30 ms 9,584 KB
testcase_111	AC	35 ms 10,088 KB
testcase_112	AC	15 ms 5,624 KB
testcase_113	AC	31 ms 9,240 KB
testcase_114	AC	20 ms 6,956 KB
testcase_115	AC	7 ms 4,376 KB
testcase_116	AC	22 ms 7,416 KB
testcase_117	AC	15 ms 5,624 KB
testcase_118	AC	40 ms 11,888 KB
testcase_119	AC	24 ms 7,996 KB
testcase_120	AC	40 ms 11,704 KB
testcase_121	AC	13 ms 5,088 KB
testcase_122	AC	23 ms 7,488 KB
testcase_123	AC	1 ms 4,376 KB
testcase_124	AC	77 ms 28,988 KB
testcase_125	AC	78 ms 28,952 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: field `n` is never read
 --> Main.rs:3:5
  |
2 | struct UnionFind {
  |        --------- field in this struct
3 |     n: usize,
  |     ^
  |
  = note: `#[warn(dead_code)]` on by default

warning: 1 warning emitted

ソースコード

raw source code

struct UnionFind {
    n: usize,
    parents: Vec<usize>,
}

impl UnionFind {
    fn new(n: usize) -> Self {
        UnionFind {
            n: n,
            parents: (0..n).collect(),
        }
    }

    fn equiv(&mut self, a: usize, b: usize) -> bool {
        self.find(a) == self.find(b)
    }
    
    fn unite(&mut self, a: usize, b: usize) {
        if self.equiv(a, b) { return; }
        let (a, b) = (a.min(b), a.max(b));
        let x = self.parents[a];
        let y = self.parents[b];
        self.parents[y] = self.parents[x];
    }

    fn find(&mut self, a: usize) -> usize {
        if self.parents[a] == a { return a; }
        let p = self.find(self.parents[a]);
        self.parents[a] = p;
        p
    }
}

fn dfs(cur: usize, prev: usize, goal: usize, paths: &Vec<Vec<(usize, usize)>>, used: &mut Vec<usize>) -> bool {
    if cur == goal {
        return true;
    }
    for &(v, bidx) in paths[cur].iter() {
        if v == prev { continue; }
        used.push(bidx);
        if dfs(v, cur, goal, paths, used) {
            return true;
        }
        used.pop();
    }
    false
}

fn main() {
    let mut n = String::new();
    std::io::stdin().read_line(&mut n).ok();
    let n: usize = n.trim().parse().unwrap();
    let mut paths = vec![vec![]; n];
    let mut uf = UnionFind::new(n);
    let mut start = 0usize;
    let mut end = 0usize;
    let mut bridge = 0usize;
    for i in 0..n {
        let mut temp = String::new();
        std::io::stdin().read_line(&mut temp).ok();
        let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
        let u = temp[0]-1;
        let v = temp[1]-1;
        if uf.find(u) == uf.find(v) {
            start = u;
            end = v;
            bridge = i;
        } else {
            paths[u].push((v, i));
            paths[v].push((u, i));
            uf.unite(u, v);
        }
    }

    let mut used = vec![];
    dfs(start, start, end, &paths, &mut used);
    used.push(bridge);
    used.sort();
    println!("{}", used.len());
    println!("{}", used.iter().map(|v| (v+1).to_string()).collect::<Vec<_>>().join(" "));
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード