結果
| 問題 | No.2987 Colorful University of Tree |
| ユーザー |
 akakimidori
|
| 提出日時 | 2024-12-12 19:21:20 |
| 言語 | Rust (1.83.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 42 |
コンパイルメッセージ
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
ソースコード
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 IwhereI: 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(°, q).is_none() {q += 1;}let q = q;let vc = greedy(°, 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)}