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();
}