use std::io;
use std::io::Write;
use std::str;
use std::cmp::max;
/// https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs
pub struct Scanner<R> {
reader: R,
buffer: Vec<String>,
}
impl<R: io::BufRead> Scanner<R> {
pub fn new(reader: R) -> Self {
Self {
reader,
buffer: vec![],
}
}
pub fn token<T: str::FromStr>(&mut self) -> T {
loop {
if let Some(token) = self.buffer.pop() {
return token.parse().ok().expect("Failed parse");
}
let mut input = String::new();
self.reader.read_line(&mut input).expect("Failed read");
self.buffer = input.split_whitespace().rev().map(String::from).collect();
}
}
}
fn main() {
let mut scan = Scanner::new(io::stdin().lock());
let mut out = io::BufWriter::new(io::stdout().lock());
let k = scan.token::<i32>();
let z = scan.token::<i32>();
let tab = (0..k-1).map(|_| {
let m = scan.token::<i32>();
let v: Vec<i32> = (0..m).map(|_| scan.token()).collect();
v
}).collect::<Vec<_>>();
let mut counts = (0..k).map(|i| if i == 0 { vec![0; (z+1) as usize] } else { vec![0; tab[(i-1) as usize].len()+1] }).collect::<Vec<_>>();
for i in (0usize..(k as usize)).rev() {
let mut needed = 0;
for j in 1..counts[i].len() {
if counts[i][j] == 0 {
needed += 1;
counts[i][j] += 1
}
if i > 0 {
counts[i-1][tab[i-1][j-1] as usize] += max(1, counts[i][j]);
}
}
counts[i][0] = max(0, counts[i][0] - needed);
if i > 0 {
counts[i-1][0] += counts[i][0];
}
}
writeln!(out, "{:?}", counts[0].iter().sum::<i64>()).unwrap();
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | use std::io; use std::io::Write; use std::str; use std::cmp::max; /// https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs pub struct Scanner<R> { reader: R, buffer: Vec<String>, } impl<R: io::BufRead> Scanner<R> { pub fn new(reader: R) -> Self { Self { reader, buffer: vec![], } } pub fn token<T: str::FromStr>(&mut self) -> T { loop { if let Some(token) = self.buffer.pop() { return token.parse().ok().expect("Failed parse"); } let mut input = String::new(); self.reader.read_line(&mut input).expect("Failed read"); self.buffer = input.split_whitespace().rev().map(String::from).collect(); } } } fn main() { let mut scan = Scanner::new(io::stdin().lock()); let mut out = io::BufWriter::new(io::stdout().lock()); let k = scan.token::<i32>(); let z = scan.token::<i32>(); let tab = (0..k-1).map(|_| { let m = scan.token::<i32>(); let v: Vec<i32> = (0..m).map(|_| scan.token()).collect(); v }).collect::<Vec<_>>(); let mut counts = (0..k).map(|i| if i == 0 { vec![0; (z+1) as usize] } else { vec![0; tab[(i-1) as usize].len()+1] }).collect::<Vec<_>>(); for i in (0usize..(k as usize)).rev() { let mut needed = 0; for j in 1..counts[i].len() { if counts[i][j] == 0 { needed += 1; counts[i][j] += 1 } if i > 0 { counts[i-1][tab[i-1][j-1] as usize] += max(1, counts[i][j]); } } counts[i][0] = max(0, counts[i][0] - needed); if i > 0 { counts[i-1][0] += counts[i][0]; } } writeln!(out, "{:?}", counts[0].iter().sum::<i64>()).unwrap(); } |
English