// Zadanie: kon (Konferencja)
// runda 1
// Marcin Machura <marcin.machura@hotmail.com>
use std::io::{self, Read, Write, BufWriter};
struct Scanner {
buf: Vec<u8>,
pos: usize,
}
impl Scanner {
fn new() -> Self {
let mut buf = Vec::new();
io::stdin().read_to_end(&mut buf).unwrap();
Scanner { buf, pos: 0 }
}
fn next_u32(&mut self) -> u32 {
while self.pos < self.buf.len() && self.buf[self.pos] <= b' ' {
self.pos += 1;
}
let mut val: u32 = 0;
while self.pos < self.buf.len() && self.buf[self.pos] >= b'0' {
val = val * 10 + (self.buf[self.pos] - b'0') as u32;
self.pos += 1;
}
val
}
}
/// Spotkanie: dzień (0-indeksowany), rodzic w globalnej numeracji (None = korzeń drzewa)
struct Meeting {
day: u32,
parent: Option<u32>, // globalny indeks rodzica
participants: u32, // liczba liści w poddrzewie (wypełniana w backward pass)
}
fn main() {
let mut sc = Scanner::new();
let out = io::stdout();
let mut out = BufWriter::new(out.lock());
let k = sc.next_u32() as usize; // liczba dni
let n1 = sc.next_u32() as usize; // spotkania pierwszego dnia
// meetings[i] — i-te spotkanie (od 0)
// day_offset[d] — globalny indeks pierwszego spotkania dnia d
let mut meetings: Vec<Meeting> = Vec::new();
let mut day_offset: Vec<u32> = Vec::new(); // day_offset[d] = globalny indeks pierwszego spotkania dnia d
// Budujemy strukturę drzewiastą, tak by dotrzeć do liści, bo sam algorytm będzie od tyłu
// Dzień 0 (pierwszy dzień): n1 spotkań, żadne nie ma rodzica
day_offset.push(0);
for _ in 0..n1 {
meetings.push(Meeting { day: 0, parent: None, participants: 0 });
}
// Dni 1..k-1
for d in 1..k {
let ni = sc.next_u32() as usize;
day_offset.push(meetings.len() as u32);
let prev_offset = day_offset[d - 1];
for _ in 0..ni {
let a = sc.next_u32(); // 1-indeksowany rodzic w dniu d-1, 0 = brak
let parent = if a > 0 { Some(prev_offset + (a - 1)) } else { None };
meetings.push(Meeting { day: d as u32, parent, participants: 0 });
}
}
let n = meetings.len();
day_offset.push(n as u32); // koniec ostatniego dnia
// Backward pass: participants[i] = liczba liści w poddrzewie i.
// Dzieci mają zawsze wyższy indeks niż rodzice (są z późniejszych dni),
// więc iteracja od tyłu przetwarza dzieci przed rodzicami.
for i in (0..n).rev() {
if meetings[i].participants == 0 {
meetings[i].participants = 1; // liść
}
if let Some(p) = meetings[i].parent {
meetings[p as usize].participants += meetings[i].participants;
}
}
// Sweep: suma participants na każdy dzień = pracownicy potrzebni tego dnia.
let answer: u64 = (0..k)
.map(|d| {
let start = day_offset[d] as usize;
let end = day_offset[d + 1] as usize;
meetings[start..end].iter().map(|m| m.participants as u64).sum::<u64>()
})
.max()
.unwrap_or(0);
writeln!(out, "{}", answer).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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 | // Zadanie: kon (Konferencja) // runda 1 // Marcin Machura <marcin.machura@hotmail.com> use std::io::{self, Read, Write, BufWriter}; struct Scanner { buf: Vec<u8>, pos: usize, } impl Scanner { fn new() -> Self { let mut buf = Vec::new(); io::stdin().read_to_end(&mut buf).unwrap(); Scanner { buf, pos: 0 } } fn next_u32(&mut self) -> u32 { while self.pos < self.buf.len() && self.buf[self.pos] <= b' ' { self.pos += 1; } let mut val: u32 = 0; while self.pos < self.buf.len() && self.buf[self.pos] >= b'0' { val = val * 10 + (self.buf[self.pos] - b'0') as u32; self.pos += 1; } val } } /// Spotkanie: dzień (0-indeksowany), rodzic w globalnej numeracji (None = korzeń drzewa) struct Meeting { day: u32, parent: Option<u32>, // globalny indeks rodzica participants: u32, // liczba liści w poddrzewie (wypełniana w backward pass) } fn main() { let mut sc = Scanner::new(); let out = io::stdout(); let mut out = BufWriter::new(out.lock()); let k = sc.next_u32() as usize; // liczba dni let n1 = sc.next_u32() as usize; // spotkania pierwszego dnia // meetings[i] — i-te spotkanie (od 0) // day_offset[d] — globalny indeks pierwszego spotkania dnia d let mut meetings: Vec<Meeting> = Vec::new(); let mut day_offset: Vec<u32> = Vec::new(); // day_offset[d] = globalny indeks pierwszego spotkania dnia d // Budujemy strukturę drzewiastą, tak by dotrzeć do liści, bo sam algorytm będzie od tyłu // Dzień 0 (pierwszy dzień): n1 spotkań, żadne nie ma rodzica day_offset.push(0); for _ in 0..n1 { meetings.push(Meeting { day: 0, parent: None, participants: 0 }); } // Dni 1..k-1 for d in 1..k { let ni = sc.next_u32() as usize; day_offset.push(meetings.len() as u32); let prev_offset = day_offset[d - 1]; for _ in 0..ni { let a = sc.next_u32(); // 1-indeksowany rodzic w dniu d-1, 0 = brak let parent = if a > 0 { Some(prev_offset + (a - 1)) } else { None }; meetings.push(Meeting { day: d as u32, parent, participants: 0 }); } } let n = meetings.len(); day_offset.push(n as u32); // koniec ostatniego dnia // Backward pass: participants[i] = liczba liści w poddrzewie i. // Dzieci mają zawsze wyższy indeks niż rodzice (są z późniejszych dni), // więc iteracja od tyłu przetwarza dzieci przed rodzicami. for i in (0..n).rev() { if meetings[i].participants == 0 { meetings[i].participants = 1; // liść } if let Some(p) = meetings[i].parent { meetings[p as usize].participants += meetings[i].participants; } } // Sweep: suma participants na każdy dzień = pracownicy potrzebni tego dnia. let answer: u64 = (0..k) .map(|d| { let start = day_offset[d] as usize; let end = day_offset[d + 1] as usize; meetings[start..end].iter().map(|m| m.participants as u64).sum::<u64>() }) .max() .unwrap_or(0); writeln!(out, "{}", answer).unwrap(); } |
English