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

提出ソース

結果

問題	No.1254 補強への架け橋
ユーザー	phspls
提出日時	2023-01-08 15:26:25
言語	Rust (1.77.0)
結果	AC
実行時間	101 ms / 2,000 ms
コード長	2,143 bytes
コンパイル時間	20,673 ms
コンパイル使用メモリ	378,636 KB
実行使用メモリ	29,096 KB
最終ジャッジ日時	2024-05-09 07:32:48
合計ジャッジ時間	24,257 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 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	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	1 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	1 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	1 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	1 ms 5,376 KB
testcase_27	AC	1 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	AC	1 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	1 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	1 ms 5,376 KB
testcase_38	AC	1 ms 5,376 KB
testcase_39	AC	1 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	1 ms 5,376 KB
testcase_42	AC	1 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	1 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	1 ms 5,376 KB
testcase_47	AC	1 ms 5,376 KB
testcase_48	AC	1 ms 5,376 KB
testcase_49	AC	1 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	1 ms 5,376 KB
testcase_52	AC	1 ms 5,376 KB
testcase_53	AC	1 ms 5,376 KB
testcase_54	AC	1 ms 5,376 KB
testcase_55	AC	1 ms 5,376 KB
testcase_56	AC	1 ms 5,376 KB
testcase_57	AC	2 ms 5,376 KB
testcase_58	AC	1 ms 5,376 KB
testcase_59	AC	1 ms 5,376 KB
testcase_60	AC	1 ms 5,376 KB
testcase_61	AC	1 ms 5,376 KB
testcase_62	AC	1 ms 5,376 KB
testcase_63	AC	5 ms 5,376 KB
testcase_64	AC	2 ms 5,376 KB
testcase_65	AC	3 ms 5,376 KB
testcase_66	AC	3 ms 5,376 KB
testcase_67	AC	2 ms 5,376 KB
testcase_68	AC	3 ms 5,376 KB
testcase_69	AC	4 ms 5,376 KB
testcase_70	AC	2 ms 5,376 KB
testcase_71	AC	2 ms 5,376 KB
testcase_72	AC	4 ms 5,376 KB
testcase_73	AC	2 ms 5,376 KB
testcase_74	AC	4 ms 5,376 KB
testcase_75	AC	3 ms 5,376 KB
testcase_76	AC	1 ms 5,376 KB
testcase_77	AC	3 ms 5,376 KB
testcase_78	AC	4 ms 5,376 KB
testcase_79	AC	4 ms 5,376 KB
testcase_80	AC	4 ms 5,376 KB
testcase_81	AC	5 ms 5,376 KB
testcase_82	AC	5 ms 5,376 KB
testcase_83	AC	62 ms 12,544 KB
testcase_84	AC	60 ms 12,288 KB
testcase_85	AC	30 ms 8,320 KB
testcase_86	AC	48 ms 10,880 KB
testcase_87	AC	52 ms 11,648 KB
testcase_88	AC	7 ms 5,376 KB
testcase_89	AC	54 ms 12,460 KB
testcase_90	AC	32 ms 8,704 KB
testcase_91	AC	24 ms 7,424 KB
testcase_92	AC	12 ms 5,376 KB
testcase_93	AC	39 ms 10,240 KB
testcase_94	AC	40 ms 9,600 KB
testcase_95	AC	37 ms 9,600 KB
testcase_96	AC	51 ms 11,904 KB
testcase_97	AC	21 ms 6,528 KB
testcase_98	AC	53 ms 12,032 KB
testcase_99	AC	27 ms 8,064 KB
testcase_100	AC	50 ms 12,800 KB
testcase_101	AC	11 ms 5,376 KB
testcase_102	AC	6 ms 5,376 KB
testcase_103	AC	13 ms 5,376 KB
testcase_104	AC	17 ms 5,888 KB
testcase_105	AC	42 ms 10,240 KB
testcase_106	AC	21 ms 6,912 KB
testcase_107	AC	58 ms 12,416 KB
testcase_108	AC	52 ms 12,288 KB
testcase_109	AC	46 ms 10,368 KB
testcase_110	AC	39 ms 9,472 KB
testcase_111	AC	44 ms 9,984 KB
testcase_112	AC	18 ms 5,760 KB
testcase_113	AC	38 ms 9,344 KB
testcase_114	AC	24 ms 6,784 KB
testcase_115	AC	9 ms 5,376 KB
testcase_116	AC	27 ms 7,680 KB
testcase_117	AC	18 ms 5,760 KB
testcase_118	AC	56 ms 11,904 KB
testcase_119	AC	30 ms 8,064 KB
testcase_120	AC	52 ms 11,520 KB
testcase_121	AC	16 ms 5,376 KB
testcase_122	AC	27 ms 7,424 KB
testcase_123	AC	1 ms 5,376 KB
testcase_124	AC	100 ms 29,096 KB
testcase_125	AC	101 ms 29,096 KB

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

コンパイルメッセージ

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

ソースコード

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

結果

テストケース

コンパイルメッセージ

ソースコード