結果

問題 No.382 シャイな人たち (2)
コンテスト
ユーザー akakimidori
提出日時 2020-05-11 22:08:23
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 2,980 bytes
コンパイル時間 24,643 ms
コンパイル使用メモリ 378,208 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-07-19 06:51:35
合計ジャッジ時間 42,129 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::collections::*;

struct RNG {
    s: usize
}

impl RNG {
    fn new(seed: usize) -> Self {
        RNG {
            s: seed,
        }
    }
    fn next(&mut self) -> usize {
        self.s = self.s * 12345 % 1000003;
        self.s
    }
}

struct Graph {
    map: BTreeMap<usize, BTreeSet<usize>>,
}

impl Graph {
    fn new() -> Self {
        Graph {
            map: BTreeMap::new(),
        }
    }
    fn insert_vertex(&mut self, v: usize, set: BTreeSet<usize>) {
        for u in set.iter() {
            self.map.get_mut(u).unwrap().insert(v);
        }
        assert!(self.map.insert(v, set).is_none());
    }
    fn add_edge(&mut self, v: usize, u: usize) {
        assert!(v != u);
        assert!(self.map.get_mut(&v).unwrap().insert(u));
        assert!(self.map.get_mut(&u).unwrap().insert(v));
    }
    fn remove_vertex(&mut self, v: usize) -> BTreeSet<usize> {
        let set = self.map.remove(&v).unwrap();
        for u in set.iter() {
            assert!(self.map.get_mut(u).unwrap().remove(&v));
        }
        set
    }
    fn calc_mis(&mut self) -> BTreeSet<usize> {
        if self.map.is_empty() {
            return BTreeSet::new();
        }
        if let Some((&v, _)) = self.map.iter().find(|p| p.1.len() <= 1) {
            let set = self.remove_vertex(v);
            let mut p = vec![];
            for &u in set.iter() {
                p.push((u, self.remove_vertex(u)));
            }
            let mut res = self.calc_mis();
            res.insert(v);
            for (u, set) in p.into_iter().rev() {
                self.insert_vertex(u, set);
            }
            self.insert_vertex(v, set);
            return res;
        }
        let v = *self.map.iter().max_by_key(|p| p.1.len()).unwrap().0;
        let set = self.remove_vertex(v);
        let mut ans = self.calc_mis();
        let mut p = vec![];
        for &u in set.iter() {
            p.push((u, self.remove_vertex(u)));
        }
        let mut q = self.calc_mis();
        q.insert(v);
        if ans.len() < q.len() {
            ans = q;
        }
        for (u, set) in p.into_iter().rev() {
            self.insert_vertex(u, set);
        }
        self.insert_vertex(v, set);
        ans
    }
}

fn run() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut rng = RNG::new(s.trim().parse().unwrap());
    let n: usize = rng.next() % 120 + 2;
    let mut graph = Graph::new();
    for i in 1..=n {
        graph.insert_vertex(i, BTreeSet::new());
    }
    let p = rng.next();
    for i in 1..=n {
        for j in (i + 1)..=n {
            let e = rng.next();
            if e >= p {
                graph.add_edge(i, j);
            }
        }
    }
    let ans = graph.calc_mis();
    let mut out = String::new();
    out.push_str(&format!("{}\n", ans.len() + 1));
    for a in ans {
        out.push_str(&format!("{} ", a));
    }
    out.pop();
    println!("{}", out);
}

fn main() {
    run();
}
0