COCI-23 (2023) - Γύρος #4 - 3 (Lepeze)

View as PDF

Submit solution

All submissions

Best submissions

Points: 40 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

HSIN

Problem type

Allowed languages

C, C++, Java, Pascal, Python

Lepeze

Ο μικρός Φραν έλαβε ως δώρο ένα ξύλινο πλαίσιο σε σχήμα κανονικού πολυγώνου. Καθώς το πολύγωνο έχει $n$ ~n~ κορυφές, έλαβε επίσης $\frac{n(n-3)}{2}$ ~\frac{n(n-3)}{2}~ ξύλινες ράβδους που ταιριάζουν με κάθε δυνατή διαγώνιο. Οι κορυφές του πολυγώνου φέρουν ετικέτες με ακεραίους αριθμούς από $1$ ~1~ έως $n$ ~n~ σε σειρά αντίθετη της φοράς των δεικτών του ρολογιού. Αρχικά, ο Φραν τοποθέτησε $n - 3$ ~n - 3~ ράβδους μέσα στο πλαίσιο με τέτοιο τρόπο ώστε κάθε ράβδος να ακουμπά δύο μη γειτονικές κορυφές του πλαισίου, και να μην υπάρχουν δύο ράβδοι που να διασταυρώνονται. Με άλλα λόγια, δημιούργησε μια τριγωνοποίηση. Μιας και αυτό από μόνο του δεν ήταν αρκετά ενδιαφέρον για αυτόν, αποφάσισε να παίξει με αυτήν τη διάταξη εφαρμόζοντας μια συγκεκριμένη διαδικασία αποτελούμενη από δύο βήματα:

Αφαίρεση μιας ράβδου.
Προσθήκη μιας νέας ράβδου έτσι ώστε να προκύπτει μια νέα τριγωνοποίηση.

Χαρακτηρίζουμε τη διαδικασία με ένα ταξινομημένο ζεύγος ανεξάρτητων ζευγαριών ( $(a,\;b)$ ~(a,\;b)~, $(c,\;d)$ ~(c,\;d)~), το οποίο σημαίνει ότι ο μικρός Φραν αφαίρεσε μια ράβδο που ακουμπούσε τις κορυφές $a$ ~a~ και $b$ ~b~, και πρόσθεσε μια ράβδο που ακουμπά τις κορυφές $c$ ~c~ και $d$ ~d~.

Ο Φραν αγαπά τους ανεμιστήρες, οπότε, κατά τη διάρκεια αυτών των διαδικασιών, καμιά φορά αναρωτιέται: "Πόσες διαδικασίες χρειάζονται για να μετατραπεί αυτή η τριγωνοποίηση σε μια τριγωνοποίηση με "ανεμιστήρα" στην κορυφή $x$ ~x~ και, με πόσους τρόπους είναι αυτό εφικτό;".

Δεδομένου ότι είναι απασχολημένος με τις διαδικασίες και διασκεδάζει, ζητά τη βοήθειά σας!

Η τριγωνοποίηση με "ανεμιστήρα" στην κορυφή $x$ ~x~ είναι μια τριγωνοποίηση όπου όλες οι διαγώνιοι έχουν ένα κοινό άκρο, δηλαδή την κορυφή $x$ ~x~.

Έστω $m$ ~m~, ο αριθμός των απαιτούμενων διαδικασιών. Έστω τώρα $f_{1}$ ~f_{1}~, $f_{2}$ ~f_{2}~, $...$ ~...~, $f_{m}$ ~f_{m}~, μια ακολουθία διαδικασιών που, όταν εφαρμοστούν με τη δεδομένη σειρά, επιτυγχάνεται η επιθυμητή τριγωνοποίηση, και έτσι αντιπροσωπεύει έναν τρόπο επίτευξής της. Έστω $s_{1}$ ~s_{1}~, $s_{2}$ ~s_{2}~, $...$ ~...~, $s_{m}$ ~s_{m}~ άλλη μια τέτοια ακολουθία. Δύο ακολουθίες είναι διαφορετικές μεταξύ τους αν υπάρχει ένα δείκτης $i$ ~i~ τέτοιος ώστε $f_{i} \neq s_{i}$ ~f_{i} \neq s_{i}~.

Καθώς ο αριθμός τέτοιων ακολουθιών μπορεί να είναι τεράστιος, ο μικρός Φραν ενδιαφέρεται μόνο για το υπόλοιπο της διαίρεσης τους με το $10^{9} + 7$ ~10^{9} + 7~.

Είσοδος

Στην πρώτη γραμμή θα υπάρχουν οι ακέραιοι $n$ ~n~ και $q$ ~q~ $(4 \le n \le 2 \cdot 10^{5},\;1 \le q \le 2 \cdot 10^{5})$ , ο αριθμός των κορυφών και ο αριθμός των συμβάντων.

Σε κάθε από τις επόμενες $n - 3$ ~n - 3~ γραμμές θα υπάρχουν οι ακέραιοι $x_{i}$ ~x_{i}~, $y_{i}$ ~y_{i}~ $(1 \le x_{i},y_{i} \le n)$ ~(1 \le x_{i},y_{i} \le n)~, οι ετικέτες των κορυφών που ακουμπά η $i$ ~i~-οστή ράβδος.

Σε κάθε από τις επόμενες $q$ ~q~ γραμμές υπάρχει ο ακέραιος $t_{i}$ ~t_{i}~ $(1 \le t_{i} \le 2)$ ~(1 \le t_{i} \le 2)~ που αντιπροσωπεύει τον τύπο του συμβάντος.

Εάν $t_{i} = 1$ ~t_{i} = 1~, ακολουθούν $4$ ~4~ ακέραιοι $a_{i}$ ~a_{i}~, $b_{i}$ ~b_{i}~, $c_{i}$ ~c_{i}~, $d_{i}$ ~d_{i}~ $(1 \le a_{i},\;b_{i},\;c_{i},\;d_{i} \le n)$ που υποδηλώνουν ότι μια διαδικασία ( $(a_{i},\;b_{i})$ ~(a_{i},\;b_{i})~, $(c_{i},\;d_{i})$ ~(c_{i},\;d_{i})~) πραγματοποιείται αυτή τη στιγμή. Είναι εγγυημένο ότι η συγκεκριμένη διαδικασία μπορεί να πραγματοποιηθεί.

Εάν $t_{i} = 2$ ~t_{i} = 2~, ακολουθεί ένας ακέραιος $x_{i}\;(1 \le x_{i} \le n)$ ~x_{i}\;(1 \le x_{i} \le n)~, που σημαίνει ότι ο μικρός Φραν ενδιαφέρεται για δεδομένα για την τριγωνοποίηση "ανεμιστήρα" στην κορυφή $x_{i}$ ~x_{i}~ σε σχέση με την τρέχουσα τριγωνοποίηση.

Έξοδος

Για κάθε συμβάν τύπου $2$ ~2~, με τη σειρά που εμφανίζονται στην είσοδο, εξάγετε δύο ακέραιους, το ελάχιστο πλήθος διαδικασιών που απαιτούνται και το πλήθος των τρόπων να φτάσετε στην επιθυμητή τριγωνοποίηση χρησιμοποιώντας τον ελάχιστο αριθμό διαδικασιών.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
$1$ ~1~	$12$ ~12~	$n \le 9,q \le 1000$ ~n \le 9,q \le 1000~
$2$ ~2~	$16$ ~16~	$x_{i} = 1$ ~x_{i} = 1~, $y_{i} = i + 2$ ~y_{i} = i + 2~ για κάθε $i = 1, ..., n - 3$ ~i = 1, ..., n - 3~ και δεν υπάρχουν συμβάντα τύπου 1
$3$ ~3~	$30$ ~30~	$q = 1$ ~q = 1~
$4$ ~4~	$12$ ~12~	$n, q \le 1000$ ~n, q \le 1000~
$5$ ~5~	$40$ ~40~	Κανένας επιπλέον περιορισμός

Παραδείγματα

input

output

0 1
1 1

Επεξήγηση του πρώτου παραδείγματος:

Η αρχική τριγωνοποίηση έχει ήδη μορφή "ανεμιστήρα" στην κορυφή $1$ ~1~, οπότε ο μικρός Φραν δεν χρειάζεται να πραγματοποιήσει καμία διαδικασία, για την οποία να υπάρχει μόνο ένας τρόπος εκτέλεσης. Μετά την εκτέλεση μιας συγκεκριμένης διαδικασίας, υπάρχει πλέον μόνο ένας τρόπος να την επαναφέρετε στην προηγούμενη κατάσταση, και αυτό είναι να εφαρμόσετε τη διαδικασία ( $(2, \;4)$ ~(2, \;4)~, $(1,\;3)$ ~(1,\;3)~).

input

output

1 1
2 1
1 1

Επεξήγηση του δεύτερου παραδείγματος:

Μοναδική ακολουθία διαδικασιών για το πρώτο ερώτημα: ( $(3,\;5)$ ~(3,\;5)~, $(1,\;4)$ ~(1,\;4)~).
Μοναδική ακολουθία διαδικασιών για το δεύτερο ερώτημα: ( $(1,\;3)$ ~(1,\;3)~, $(2,\;5)$ ~(2,\;5)~), ( $(3,\;5)$ ~(3,\;5)~, $(2,\;4)$ ~(2,\;4)~).
Μοναδική ακολουθία διαδικασιών για το τρίτο ερώτημα: ( $(3,\;5)$ ~(3,\;5)~, $(2,\;5)$ ~(2,\;5)~).

input

output

4 12
3 6

Comments

There are no comments at the moment.