38ος ΠΔΠ Γ' Φάση
Παγωτομηχανές (icecream)
[ Μονάδες]
Ο Τάκης ονειρεύεται ότι έχει \(N\) πιτσαρίες, αριθμημένες από το \(1\) έως και το \(N\). Η πιτσαρία \(1\) θεωρείται κεντρική, μιας και έχει συναισθηματική αξία για τον Τάκη. Κάθε άλλη πιτσαρία \(i\) (με \(i > 1\)) αποτελεί παράρτημα μίας άλλης πιτσαρίας \(p_i\) (ισχύει \(p_i < i\)). Αντίστοιχα, θα λέμε ότι η πιτσαρία \(p_i\) είναι μητρική της πιτσαρίας \(i\).
Οι παγωτομηχανές στις μέρες μας είναι ακριβές. Συγκεκριμένα, για να εγκαταστήσει παγωτομηχανή σε μία πιτσαρία, ο Τάκης χρειάζεται να πληρώσει κόστος \(F\).
Όταν ένας πελάτης παραγγείλει παγωτό, η πιτσαρία που λαμβάνει την παραγγελία ακολουθεί την εξής διαδικασία. Αν η πιτσαρία έχει παγωτομηχανή, εξυπηρετεί την παραγγελία. Διαφορετικά, καλεί τηλεφωνικά την μητρική της και μεταφέρει την παραγγελία σε αυτήν, με κόστος \(1\). Αυτή με τη σειρά της, ακολουθεί την ίδια διαδικασία. Έτσι, ενδέχεται μια παραγγελία να μεταφερθεί πολλές φορές μέχρι να εξυπηρετηθεί. Προσέξτε ότι, ακόμα και αν γίνουν πολλές παραγγελίες για παγωτό στην ίδια πιτσαρία, αυτές μεταφέρονται ξεχωριστά, δηλαδή κάνοντας μία τηλεφωνική κλήση για κάθε παραγγελία.
Προφανώς, επειδή η πιτσαρία \(1\) δεν έχει μητρική, ο μόνος τρόπος να εξυπηρετηθούν παραγγελίες που φτάνουν σε αυτή είναι να έχει παγωτομηχανή.
Προκειμένου να σχεδιάσει το νέο του εγχείρημα, ο Τάκης έχει φανταστεί \(Q\) σενάρια. Κάθε σενάριο αποτελείται από \(k_i\) πιτσαρίες, διαφορετικές μεταξύ τους, στις οποίες υπάρχει αρχικά μία παραγγελία με παγωτό. Ο Τάκης θέλει να υπολογίσει το ελάχιστο συνολικό κόστος για να εξυπηρετήσει όλες τις παραγγελίες. Αυτό περιλαμβάνει και το κόστος για να αγοράσει παγωτομηχανές και το τηλεφωνικό κόστος μέχρι να εξυπηρετηθούν οι παραγγελίες. Τα σενάρια είναι ανεξάρτητα μεταξύ τους, επομένως επιτρέπεται στο καθένα να τοποθετεί τις παγωτομηχανές σε διαφορετικές πιτσαρίες.
Δεδομένα εισόδου (stdin)
Η πρώτη γραμμή περιέχει τρεις ακέραιους αριθμούς \(N\), \(Q\), \(F\): το πλήθος πιτσαρίων, το πλήθος σεναρίων και το κόστος αγοράς κάθε παγωτομηχανής. Η δεύτερη γραμμή περιέχει \(N-1\) ακέραιους αριθμούς \(p_2, \ldots, p_N\): την ακολουθία που περιέχει τη μητρική πιτσαρία κάθε πιτσαρίας. Ακολουθούν \(Q\) γραμμές. Ο πρώτος αριθμός που περιέχει καθεμία από αυτές είναι ένας θετικός ακέραιος \(k_i\): το πλήθος πιτσαρίων στο αντίστοιχο σενάριο. Ακολουθούν \(k_i\) θετικοί ακέραιοι \(r_{i,1}, \ldots , r_{i,k_i}\): οι αριθμοί των πιτσαρίων στις οποίες αρχικά υπάρχει παραγγελία με παγωτό στο αντίστοιχο σενάριο.
Δεδομένα εξόδου (stdout)
Πρέπει να αποτελείται από \(Q\) γραμμές, καθεμία από τις οποίες να περιέχει έναν ακέραιο αριθμό: την απάντηση του αντίστοιχου σεναρίου.
Παράδειγμα εισόδου-εξόδου
| stdin | stdout |
|---|---|
| 6 1 2 1 1 2 4 5 4 3 4 5 6 |
7 |
Εξήγηση παραδείγματος: Μπορεί να αποδειχθεί ότι το ελάχιστο δυνατό συνολικό κόστος για το σενάριο \([3, 4, 5, 6]\) είναι \(7\) και ένας τρόπος να το πετύχουμε είναι τοποθετώντας παγωτομηχανή στις πιτσαρίες \(3\) και \(4\), με κόστος \(2+2=4\). Οι παραγγελίες που αρχικά βρίσκονται στις πιτσαρίες \(3\) και \(4\) εξυπηρετούνται χωρίς κόστος, η παραγγελία της πιτσαρίας \(5\) εξυπηρετείται με κόστος \(1\) και η παραγγελία της πιτσαρίας \(6\) εξυπηρετείται με κόστος \(2\).
Περιορισμοί
- \(2 \leq N \leq 200.000\).
- \(1 \leq Q \leq 10.000\).
- \(1 \leq F \leq 10^{18}\).
- \(1 \leq p_i < i\).
- \(1 \leq k_i \leq N\).
- \(1 \leq r_{i,j} \leq N\).
- Σε κάθε σενάριο, οι πιτσαρίες \(r_{i,1}, \ldots , r_{i,k_i}\) είναι διαφορετικές μεταξύ τους
- Το άθροισμα των \(k_i\) όλων των σεναρίων είναι το πολύ \(10.000\).
Υποπροβλήματα
- (8 βαθμοί) \(F = 1\).
- (11 βαθμοί) \(F = 10^{18}\), \(Q = 1\).
- (12 βαθμοί) \(k_i = 2\), για κάθε \(i\) (\(1 \leq i \leq Q\)).
- (13 βαθμοί) \(p_i = i-1\), για κάθε \(i\) (\(2 \leq i \leq N\)).
- (27 βαθμοί) \(N \leq 10.000\), \(Q = 1\).
- (13 βαθμοί) \(Q = 1\).
- (16 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.
Παρατηρήσεις
Μέγιστος χρόνος εκτέλεσης: \(0.75\) sec.
Μέγιστη διαθέσιμη μνήμη: \(128\) MB.