[C++] Brisbane

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 qui a destra, 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:
1.  senza comprare biglietti (solo con mezzi gratis);
2.  comprando solo il biglietto giornaliero dei bus;
3.  comprando solo il biglietto giornaliero dei traghetti;
4.  comprando entrambe le tipologie di biglietti.

Assunzioni
• 2 ≤ N ≤ 1000
• N ≤ Mg+Mb+Mt ≤ 10000

Esempi di input/output

File input.txt                 File output.txt
6 2 2 4 2                         1
1                                 1
5                                 2
0 1                               2
2 5
0 3
1 3
2 4
4 5
1 2
3 4 1

File input.txt  (corrisponde alla figura)  File output.txt
30 5 18 14 11                                          2
8                                                      5
12                                                     4
15                                                     5
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 18

Qui bisogna scrivere le città nei grafi {gratis, col bus, col treno, tutti} e contare per ogni grafo quante tappe si possono raggiungere.

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 99 100 101 102 103 104 105 106 107 108 109

#include<cstdlib> #include<iostream> #include<fstream> #include<vector> #include<algorithm> #include<cstring> #define M 10000 using namespace std; ifstream in; ofstream out; int n,a,cg,cb,ct,t1,t2,tg=0,tb=0,tt=0,tc=0; vector<int> vg[M]; vector<int> vb[M]; vector<int> vt[M]; vector<int> vc[M]; int attr[M]; bool vis[M]; void gg(int k){ //esplora il grafo gratuito e somma le fermate con punti di attrazione vis[k]=false; if (binary_search(attr,attr+a,k)) tg++; for (int i=0;i<vg[k].size();i++) if(vis[vg[k][i]]) gg(vg[k][i]);} void gb(int k){ //esplora il grafo bus e somma le fermate con punti di attrazione vis[k]=false; if (binary_search(attr,attr+a,k)) tb++; for (int i=0;i<vb[k].size();i++) if(vis[vb[k][i]]) gb(vb[k][i]);} void gt(int k){ //esplora il grafo treno e somma le fermate con punti di attrazione vis[k]=false; if (binary_search(attr,attr+a,k)) tt++; for (int i=0;i<vt[k].size();i++) if(vis[vt[k][i]]) gt(vt[k][i]);} void gc(int k){ //esplora il grafo combinato e somma le fermate con punti di attrazione vis[k]=false; if (binary_search(attr,attr+a,k)) tc++; for (int i=0;i<vc[k].size();i++) if(vis[vc[k][i]]) gc(vc[k][i]);} int main(){ in.open("input.txt"); out.open("output.txt"); in>>n>>a>>cg>>cb>>ct; for (int i=0;i<a;i++) in>>attr[i]; sort(attr,attr+a); for (int i=0;i<cg;i++){ in>>t1>>t2; vg[t1].push_back(t2); vb[t1].push_back(t2); vt[t1].push_back(t2); vc[t1].push_back(t2); vg[t2].push_back(t1); vb[t2].push_back(t1); vt[t2].push_back(t1); vc[t2].push_back(t1); } for (int i=0;i<cb;i++){ in>>t1>>t2; vb[t1].push_back(t2); vc[t1].push_back(t2); vb[t2].push_back(t1); vc[t2].push_back(t1); } for (int i=0;i<ct;i++){ in>>t1>>t2; vt[t1].push_back(t2); vc[t1].push_back(t2); vt[t2].push_back(t1); vc[t2].push_back(t1); } memset(vis,true,n); gg(0); memset(vis,true,n); gb(0); memset(vis,true,n); gt(0); memset(vis,true,n); gc(0); out<<tg<<"\n"<<tb<<"\n"<<tt<<"\n"<<tc; return 0;}