結果

問題 No.977 アリス仕掛けの摩天楼
ユーザー VvyLw
提出日時 2024-06-20 19:03:48
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 4,289 bytes
コンパイル時間 13,015 ms
コンパイル使用メモリ 401,328 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-20 19:04:02
合計ジャッジ時間 14,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(unused_macros)]
macro_rules! rep {
    ($n: expr, $body: block) => {
        for _ in 0..$n {
            $body
        }
    };
    ($i: ident, $n: expr, $body: block) => {
        for $i in 0..$n {
            $body
        }
    };
    ($i: ident, $a: expr, $b: expr, $body: block) => {
        for $i in $a..=$b {
            $body
        }
    };
    ($i: ident, $a: expr, $b: expr, $c: expr, $body: block) => {
        let mut $i = $a;
        while $i <= $b {
            $body
            $i += $c;
        }
    };
}

macro_rules! rvp {
    ($i: ident, $n: expr, $body: block) => {
        for $i in (0..$n).rev() {
            $body
        }
    };
    ($i: ident, $a: expr, $b: expr, $body: block) => {
        for $i in ($b..=$a).rev() {
            $body
        }
    };
    ($i: ident, $a: expr, $b: expr, $c: expr, $body: block) => {
        let mut $i = $a;
        while $i >= $b {
            $body
            $i -= $c;
        }
    };
}

macro_rules! each {
    ($el: ident, $v: expr, $body: block) => {
        for $el in $v {
            $body
        }
    }
}

#[allow(dead_code)]
fn out<T: std::fmt::Display>(x: T) {
    print!("{}", x);
}
macro_rules! out {
    () => {
        println!();
    };
    ($head:expr $(, $tail:expr)*) => {
        out($head);
        $(
            print!(" ");
            out($tail);
        )*
        println!();
    };
}

#[allow(dead_code)]
const MOD: i32 = 998244353;
#[allow(dead_code)]
const M0D: i32 = 1e9 as i32 + 7;
#[allow(dead_code)]
const INF: i32 = 1 << 30;
#[allow(dead_code)]
const LINF: i64 = (1 << 61) - 1;
#[allow(dead_code)]
#[allow(non_upper_case_globals)]
const dx: [i32; 9] = [0, -1, 1, 0, 0, -1, -1, 1, 1];
#[allow(dead_code)]
#[allow(non_upper_case_globals)]
const dy: [i32; 9] = [0, 0, 0, -1, 1, -1, 1, -1, 1];
const MULTI: bool = false;

pub fn main() {
    rep!(match MULTI {
        true => {
            let mut num = String::new();
            std::io::stdin().read_line(&mut num).expect("invalid input");
            num.parse().unwrap()
        }
        _ => 1
    }, {
        solve();
    });
}

fn solve() {
    proconio::input!{n: usize}
    let mut uf = UnionFind::new(n);
    let mut gg = true;
    let mut cnt = vec![0; n];
    for _ in 0..n - 1 {
        proconio::input! {
            u: usize,
            v: usize
        }
        gg &= uf.unite(u, v);
        cnt[u] += 1;
        cnt[v] += 1;
    }
    if gg {
        return println!("Bob");
    }
    if cnt.iter().any(|&e| e >= 1 && e != 2) {
        return println!("Alice");
    }
    out!(match uf.size(0) == n - 1 || uf.size(1) == n - 1 {
        true => "Bob",
        _ => "Alice"
    });
}

pub trait DSU {
    fn new(n: usize) -> Self;
    fn root(&mut self, i: usize) -> usize;
    fn size(&mut self, i: usize) -> usize;
    fn unite(&mut self, i: usize, j: usize) -> bool;
    fn same(&mut self, i: usize, j: usize) -> bool {
        self.root(i) == self.root(j)
    }
    fn groups(&mut self) -> Vec<Vec<usize>>;
}

pub struct UnionFind {
    par: Vec<i32>
}
impl DSU for UnionFind {
    fn new(n: usize) -> Self {
        Self { par: vec![-1; n] }
    }
    fn root(&mut self, i: usize) -> usize {
        if self.par[i] >= 0 {
            self.par[i] = self.root(self.par[i] as usize) as i32;
            self.par[i] as usize
        } else {
            i
        }
    }
    fn size(&mut self, i: usize) -> usize {
        let id = self.root(i);
        -self.par[id] as usize as usize
    }
    fn unite(&mut self, mut i: usize, mut j: usize) -> bool {
        i = self.root(i);
        j = self.root(j);
        if i == j {
            return false;
        }
        if i > j {
            std::mem::swap(&mut i, &mut j);
        }
        self.par[i] += self.par[j];
        self.par[j] = i as i32;
        true
    }
    fn groups(&mut self) -> Vec<Vec<usize>> {
        let n = self.par.len();
        let mut res = vec![Vec::new(); n];
        for i in 0..n {
            res[self.root(i)].push(i);
        }
        res.into_iter().filter(|g| !g.is_empty()).collect()
    }
}

pub fn is_bipartite(mut uf: UnionFind) -> bool {
    assert_eq!(uf.par.len() % 2, 0);
    let n = uf.par.len() / 2;
    let mut ok = true;
    for i in 0..n {
        ok &= uf.root(i) != uf.root(i + n);
    }
    ok
}
0