結果

問題 No.2987 Colorful University of Tree
ユーザー akakimidoriakakimidori
提出日時 2024-12-12 19:21:20
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 1,036 ms / 5,000 ms
コード長 8,404 bytes
コンパイル時間 17,488 ms
コンパイル使用メモリ 379,092 KB
実行使用メモリ 131,648 KB
最終ジャッジ日時 2024-12-12 19:22:52
合計ジャッジ時間 44,964 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 150 ms
5,248 KB
testcase_03 AC 166 ms
5,248 KB
testcase_04 AC 167 ms
5,248 KB
testcase_05 AC 640 ms
75,940 KB
testcase_06 AC 108 ms
24,396 KB
testcase_07 AC 120 ms
21,892 KB
testcase_08 AC 728 ms
79,972 KB
testcase_09 AC 124 ms
24,516 KB
testcase_10 AC 898 ms
110,896 KB
testcase_11 AC 973 ms
102,616 KB
testcase_12 AC 897 ms
131,648 KB
testcase_13 AC 1,036 ms
102,608 KB
testcase_14 AC 1,014 ms
105,964 KB
testcase_15 AC 969 ms
120,076 KB
testcase_16 AC 945 ms
114,516 KB
testcase_17 AC 919 ms
107,440 KB
testcase_18 AC 943 ms
102,832 KB
testcase_19 AC 960 ms
105,956 KB
testcase_20 AC 1,000 ms
102,636 KB
testcase_21 AC 961 ms
102,672 KB
testcase_22 AC 474 ms
102,740 KB
testcase_23 AC 736 ms
131,408 KB
testcase_24 AC 249 ms
13,224 KB
testcase_25 AC 284 ms
13,228 KB
testcase_26 AC 246 ms
13,224 KB
testcase_27 AC 246 ms
13,224 KB
testcase_28 AC 243 ms
13,224 KB
testcase_29 AC 10 ms
5,248 KB
testcase_30 AC 69 ms
5,248 KB
testcase_31 AC 63 ms
5,248 KB
testcase_32 AC 135 ms
5,888 KB
testcase_33 AC 175 ms
16,344 KB
testcase_34 AC 220 ms
26,268 KB
testcase_35 AC 230 ms
57,108 KB
testcase_36 AC 441 ms
96,576 KB
testcase_37 AC 55 ms
16,064 KB
testcase_38 AC 219 ms
52,480 KB
testcase_39 AC 49 ms
14,780 KB
testcase_40 AC 364 ms
81,240 KB
99_evil_hack_000.txt AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `u`
   --> src/main.rs:233:32
    |
233 |             for (&color, &(dp, u, k)) in buf.iter().zip(child_color.iter()) {
    |                                ^ help: if this is intentional, prefix it with an underscore: `_u`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: type alias `Deque` is never used
  --> src/main.rs:81:6
   |
81 | type Deque<T> = VecDeque<T>;
   |      ^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}
mod util {
    pub trait Join {
        fn join(self, sep: &str) -> String;
    }

    impl<T, I> Join for I
    where
        I: Iterator<Item = T>,
        T: std::fmt::Display,
    {
        fn join(self, sep: &str) -> String {
            let mut s = String::new();
            use std::fmt::*;
            for (i, v) in self.enumerate() {
                if i > 0 {
                    write!(&mut s, "{}", sep).ok();
                }
                write!(&mut s, "{}", v).ok();
            }
            s
        }
    }
}
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let t: u32 = sc.next();
    for _ in 0..t {
        let n: usize = sc.next();
        let mut e = vec![vec![]; n];
        for e in e.iter_mut() {
            let m = sc.next::<usize>();
            e.resize(m, 0usize);
            for e in e.iter_mut() {
                *e = sc.next::<usize>() - 1;
            }
        }
        let (q, vc, ec) = solve(e.clone());
        let mut list = vec![vec![]; n - 1];
        for (e, ec) in e.iter().zip(ec.iter()) {
            for (e, ec) in e.iter().zip(ec.iter()) {
                list[*e].push(*ec);
            }
        }
        assert!(list.iter().all(|l| l[0] != l[1]));
        let mut set = Set::new();
        writeln!(out, "{}", q).ok();
        for (vc, ec) in vc.iter().zip(ec.iter()) {
            for &c in ec.iter() {
                assert!(set.insert((vc, c)));
            }
            use util::*;
            writeln!(out, "{} {}", *vc + 1, ec.iter().map(|a| *a + 1).join(" ")).ok();
        }
    }
}

fn solve(e: Vec<Vec<usize>>) -> (usize, Vec<usize>, Vec<Vec<usize>>) {
    let n = e.len();
    let mut list = vec![vec![]; n - 1];
    for (i, e) in e.iter().enumerate() {
        for (j, e) in e.iter().enumerate() {
            list[*e].push((i, j));
        }
    }
    let mut tree = vec![vec![]; n];
    for (i, v) in list.iter().enumerate() {
        let (a, b) = (v[0].0, v[1].0);
        tree[a].push((b, i));
        tree[b].push((a, i));
    }
    let deg = e.iter().map(|e| e.len()).collect::<Vec<_>>();
    let root = (0..n).max_by_key(|v| deg[*v]).unwrap();
    let mut topo = vec![root];
    let mut parent = vec![n; n];
    for i in 0..n {
        let v = topo[i];
        for (u, k) in tree[v].clone() {
            parent[u] = k;
            tree[u].retain(|p| p.0 != v);
            topo.push(u);
        }
    }
    let (list, tree, topo, parent) = (list, tree, topo, parent);
    let mut q = (1..)
        .find(|&p| p * p >= 2 * (n - 1))
        .unwrap()
        .max(*deg.iter().max().unwrap());
    if greedy(&deg, q).is_none() {
        q += 1;
    }
    let q = q;
    let vc = greedy(&deg, q).unwrap();
    let mut memo = vec![vec![]; q];
    for (i, vc) in vc.iter().enumerate() {
        memo[*vc].push(i);
    }
    let mut ans = vec![];
    while {
        let mut used = vec![false; q];
        let mut color_list = vec![vec![]; n];
        for memo in memo.iter() {
            let sum = memo.iter().map(|v| deg[*v]).sum::<usize>();
            if 2 * sum <= q {
                for &v in memo.iter() {
                    let mut c = vec![0; deg[v]];
                    for c in c.iter_mut() {
                        let mut x = rand() % q;
                        while used[x] {
                            x = rand() % q;
                        }
                        *c = x;
                        used[x] = true;
                    }
                    color_list[v] = c;
                }
                for x in memo.iter().flat_map(|v| color_list[*v].iter()) {
                    used[*x] = false;
                }
            } else {
                let mut perm = (0..q).collect::<Vec<_>>();
                shuffle(&mut perm);
                for &v in memo.iter() {
                    let mut c = vec![0; deg[v]];
                    for c in c.iter_mut() {
                        *c = perm.pop().unwrap();
                    }
                    color_list[v] = c;
                }
            }
        }
        let mut tmp = e.iter().map(|e| vec![q; e.len()]).collect::<Vec<_>>();
        let mut dp = vec![q; n];
        for &v in topo.iter().rev() {
            let mut child_color = vec![];
            for &(u, k) in tree[v].iter() {
                child_color.push((dp[u], u, k));
            }
            child_color.sort();
            let mut pos = Map::new();
            for (i, &(c, _, _)) in child_color.iter().enumerate() {
                pos.entry(c).or_insert((i, i)).1 = i;
            }
            let mut clist = std::mem::take(&mut color_list[v]);
            let mut buf = vec![!0; clist.len()];
            let mut range = (0, clist.len());
            for c in clist.iter_mut() {
                if let Some(&(l, r)) = pos.get(c) {
                    range.0 = range.0.max(r - l + 1);
                    buf[l] = *c;
                    *c = !0;
                }
            }
            if v == root && range.0 == range.1 {
                break;
            }
            assert!(range.0 < range.1);
            clist.retain(|c| *c != !0);
            for buf in buf.iter_mut() {
                if *buf == !0 {
                    *buf = clist.pop().unwrap();
                }
            }
            let shift = rand() % (range.1 - range.0) + range.0;
            buf.rotate_right(shift);
            for (&color, &(dp, u, k)) in buf.iter().zip(child_color.iter()) {
                assert!(dp != color);
                let pos = list[k].iter().find(|p| p.0 == v).unwrap().1;
                tmp[v][pos] = color;
            }
            if v != root {
                let c = buf.pop().unwrap();
                dp[v] = c;
                let k = parent[v];
                let pos = list[k].iter().find(|p| p.0 == v).unwrap().1;
                tmp[v][pos] = c;
            }
            if v == root {
                ans = tmp;
                break;
            }
        }
        ans.is_empty()
    } {}
    (q, vc, ans)
}

fn greedy(a: &[usize], q: usize) -> Option<Vec<usize>> {
    let n = a.len();
    assert!(a.iter().sum::<usize>() == 2 * (n - 1));
    let mut rem = vec![q; q];
    let mut h = std::collections::BinaryHeap::new();
    for i in 0..q {
        h.push((q, i));
    }
    let mut ans = vec![0; n];
    let mut ord = (0..n).collect::<Vec<_>>();
    ord.sort_by_key(|v| a[*v]);
    for x in ord.into_iter().rev() {
        let a = a[x];
        let ans = &mut ans[x];
        let (_, k) = h.pop().unwrap();
        if rem[k] < a {
            return None;
        }
        *ans = k;
        rem[k] -= a;
        h.push((rem[k], k));
    }
    Some(ans)
}
0