Messaggi

di

Luca sta preparando un sistema di messaggistica semplice per consentire la comunicazione tra gli studenti (soprattutto durante le verifiche, un sistema simile torna sempre utile).
Luca ha finito di realizzare il sistema e lo sta provando: purtroppo qualcosa non funziona e bisogna cercare di capire la situazione.
Da buon sistemista, la prima cosa che fa è analizzare il file di log conservato sul server che registra ogni singolo messaggi scambiato tra gli utenti.
Un utente è identificato con nome (con lunghezza massima 10 caratteri tra lettere minuscole e numeri).
Dopo un po’ di analisi, Luca ha capito che il problema non risiede nel server: tutti i messaggi sono memorizzati correttamente.
Probabilmente quindi è l’app che ha realizzato per gli smartphone dei suoi compagni ad avere qualche problema.

Per verificare ciò, aiutalo a rispondere a due tipi di domande:

utente INVIATI

che deve restituire l’elenco degli utenti a cui utente ha inviato un messaggio

utente RICEVUTI

che deve restituire l’elenco degli utenti da cui utente ha ricevuto un messaggio.

Così come il file di log è ordinato cronologicamente, allo stesso modo gli elenchi dell’utente dovranno essere nello stesso ordine con cui gli utenti compaiono nel log.

Dati di input

L’input è composto da 1+N+R righe.

  • La prima riga contiene due interi, N e R, rispettivamente il numero di righe del file di log (ovvero, quanti messaggi sono stati scambiati) e il numero di richieste a cui si deve rispondere.
  • Le successive N righe sono nella forma mittente destinatario e indicano che un messaggio è stato inviato da mittente a destinatario.
  • Le ultime R righe sono nella forma utente TIPORICHIESTA indicando che Luca vuole sapere l’elenco degli utenti da cui utente ha ricevuto un messaggio (nel caso di RICEVUTI) oppure l’elenco degli utenti a cui utente ha inviato un messaggio (nel caso di INVIATI)

Dati di output

L’output deve essere formato da R righe.
Ciascuna di queste righe deve contenere un intero non negativo Ui, il numero di utenti che corrispondono alla R-esima richiesta, seguito dai nomi degli utenti.

Assunzioni

  • N, R ≤ 100000.
  • Nel 50% dei casi vale che N, R ≤ 1000.

Esempi di input/output

input.txt output.txt
3 2
luca mario
luca pietro
francesca pietro
luca INVIATI
pietro RICEVUTI		 2 mario pietro
2 luca francesca

Note

  • Più messaggi possono essere inviati dallo stesso mittente anche verso lo stesso destinatario.
    Tutti i messaggi dovranno comparire nell’output del problema.
  • In ogni messaggio, il mittente non coincide mai con il destinatario.
/**
	www.valcon.it
	ABC - Messaggi
*/

#include
#include
#include
#include
#include

using namespace std;

int main()
{    
	ifstream					  fin ( "input.txt");		// input
	ofstream                      fout("output.txt");		// output
	int                           N, 					    // n. MESSAGGI
	                              R;						// n. RICHIESTE
	map< string, vector > msg_inviati;				// MESSAGGI inviati
	map< string, vector > msg_ricevuti;             // MESSAGGI ricevuti
	string                        mittente, destinatario,   // ogni MESSAGGIO
								  utente,   TIPORICHIESTA;	// ogni RICHIESTA
	vector                risposta;					// raccolta RICHIESTA
	
	fin >> N >> R;			
    for(int i=0; i < N; i++)
    {    
        fin >> mittente >> destinatario;
        
        msg_inviati [mittente    ].push_back(destinatario);
        msg_ricevuti[destinatario].push_back(mittente    );
    }
    
	for (int i=0; i < R; i++)
    {    	
        fin >> utente >> TIPORICHIESTA;
                
        	 if (TIPORICHIESTA == "INVIATI" ) risposta=msg_inviati [utente];
        else if (TIPORICHIESTA == "RICEVUTI") risposta=msg_ricevuti[utente];
        
		int quanti=risposta.size();
		fout << quanti << " ";
		for (int j=0; j < quanti; j++)
			fout << risposta[j] << " ";
		fout << endl;
    }
}