Fase Territoriale 2013
Nel 2013, le IOI si svolgeranno a Brisbane (in Australia).
La rappresentativa italiana ha già iniziato a studiare la città, per capire cosa ci sia di interessante da vedere, e come ci si possa spostare nella giornata libera successiva alla seconda gara delle Olimpiadi.
L’offerta di trasporto pubblico a Brisbane è abbastanza variegata: ci sono due linee di bus, di cui una gratuita che gira intorno alla città, e due linee di traghetti che fermano in diversi punti del fiume Brisbane, che taglia la città in due; per quello che riguarda i prezzi, esiste un abbonamento giornaliero a tutti i trasporti pubblici, bus e traghetti insieme, oppure è possibile prendere un più economico abbonamento giornaliero ai soli traghetti, o un ancor più economico abbonamento ai soli bus.La squadra italiana vorrà visitare il maggior numero di attrazioni possibile e per questo motivo Monica, la responsabile dell’organizzazione, ha deciso di cercare un buon compromesso tra il prezzo dei biglietti e le attrazioni che sarà possibile raggiungere partendo dall’hotel.
Data una lista di attrazioni e la mappa dei collegamenti delle diverse linee del trasporto pubblico, il vostro compito è quello di aiutare Monica a capire quante attrazioni sono raggiungibili per ogni possibile scelta dei biglietti per i trasporti pubblici.
Per esempio, possiamo fare riferimento alla figura, dove ad ogni fermata è associato un cerchio (o un quadrato nel caso di luogo di attrazione) e i collegamenti sono:
- tratteggiati – collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi);
- rossi – bus a pagamento;
- gialli – traghetto.
Il punto di partenza della rappresentativa italiana è la fermata numero 0; le attrazioni da vedere sono quelle rappresentate con un quadrato, numerate rispettivamente 8, 12, 15, 22 e 28.
Come si può vedere, spostandosi con i mezzi gratuiti si raggiungono solo due attrazioni (la numero 8 e la numero 14); comprando il biglietto del bus si raggiungono tutte le attrazioni; comprando il biglietto del traghetto si raggiungono, oltre alla 8 e la 14, anche la 12 e la 15 per un totale di quattro attrazioni.
Il biglietto combinato, in questo caso, raggiunge tutte le attrazioni.Dati di input
Il file input.txt è composto da 1+A+Mg+Mb+Mt righe.
- La prima riga contiene cinque interi positivi separati da uno spazio, che rappresentano il numero N delle fermate, il numero A di attrazioni, il numero Mg dei collegamenti gratuiti, il numero Mb dei collegamenti via bus e il numero Mt dei collegamenti via traghetto.
Ogni fermata è rappresentata da un intero compreso tra 0 e N-1.- Le successive A righe contengono ognuna una fermata (un intero compreso tra 0 e N-1) corrispondente ad una delle attrazioni che la rappresentativa italiana può visitare.
- Ognuna delle successive Mg+Mb+Mt righe contiene un collegamento del trasporto pubblico, rappresentato da due interi positivi: le fermate collegate.
Le prime Mg righe contengono i collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi), poi le successive Mb contengono i collegamenti del bus a pagamento e infine le ultime Mt righe contengono i collegamenti dei traghetti.
Il punto di partenza della rappresentativa italiana è la sempre la fermata numero 0.Dati di output
Il file output.txt è composto da 4 righe contenenti ognuna un intero non negativo, rispettivamente, il numero di attrazioni raggiungibili:
- senza comprare biglietti (solo con mezzi gratis);
- comprando solo il biglietto giornaliero dei bus;
- comprando solo il biglietto giornaliero dei traghetti;
- comprando entrambe le tipologie di biglietti.
Assunzioni
- 2 ≤ N ≤ 1000
- N ≤ Mg+Mb+Mt ≤ 10000
Esempi di input/output
input.txt output.txt 6 2 2 4 2
1
5
0 1
2 5
0 3
1 3
2 4
4 5
1 2
3 41
1
2
230 5 18 14 11
8
12
15
22
28
0 5
0 24
1 8
1 25
2 3
2 23
5 11
8 14
11 16
13 17
14 19
16 20
18 22
19 21
20 22
21 22
23 24
23 25
1 4
2 28
2 29
4 7
4 8
7 29
12 26
14 15
15 19
15 21
17 21
18 21
26 27
27 28
3 7
3 25
6 9
6 13
7 15
9 10
10 17
12 16
12 18
13 15
17 182
5
4
5Nota
- Il secondo caso di esempio corrisponde alla situazione presentata in figura.
/* www.valcon.it OII 2013 - Fase territoriale - A spasso per Brisbane */ #include#include #include using namespace std; #define NMAX 1000 ifstream fin ; ofstream fout; vector fermateG[NMAX]; vector fermateB[NMAX]; vector fermateT[NMAX]; vector fermate [NMAX]; bool visitate [NMAX]; bool attrazioni[NMAX]; int N, A, Mg, Mb, Mt; int contatore; void visita(int fermata, vector collegamenti[]) { if(!visitate[fermata]) { visitate[fermata]=true; if(attrazioni[fermata]) contatore++; for(int i=0; i < collegamenti[fermata].size(); i++) visita(collegamenti[fermata][i], collegamenti); } } void visitare(vector collegamenti[]) { contatore=0; for(int i=0; i < N; i++) visitate[i]=false; visita(0, collegamenti); fout << contatore << endl; } int main() { fin.open( "input.txt"); fout.open("output.txt"); fin >> N >> A >> Mg >> Mb >> Mt; int part,dest; for(int i=0; i < N; i++) { attrazioni[i]=false; } for(int i=1; i <= A; i++) { fin >> part; attrazioni[part]=true; } for(int i=1; i <= Mg; i++) { fin >> part >> dest; fermate [part].push_back(dest); fermate [dest].push_back(part); fermateG[part].push_back(dest); fermateG[dest].push_back(part); fermateB[part].push_back(dest); fermateB[dest].push_back(part); fermateT[part].push_back(dest); fermateT[dest].push_back(part); } for(int i=1; i <= Mb; i++) { fin >> part >> dest; fermate [part].push_back(dest); fermate [dest].push_back(part); fermateB[part].push_back(dest); fermateB[dest].push_back(part); } for(int i=1; i <= Mt; i++) { fin >> part >> dest; fermate [part].push_back(dest); fermate [dest].push_back(part); fermateT[part].push_back(dest); fermateT[dest].push_back(part); } visitare(fermateG); visitare(fermateB); visitare(fermateT); visitare(fermate ); return 0; }