Musical fight (trap) 79/100

Salve, sto provando a risolverre il problema Musical fight (itoi_trap), ma uno o due testcase dell’ultimo subtask vanno fouri tempo, e non so come renderlo più efficiente. Ecco il codice:

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// input data
int N, L;



int main() {
    //  uncomment the following lines if you want to read/write from files
    //  freopen("input.txt", "r", stdin);
    //  freopen("output.txt", "w", stdout);
    std::unordered_map <std::string, int> mp;
    std::vector<std::string> s0;
    std::cin >> N >> L;
    int M;
    std::cin >> M;
    for (int j = 0; j < M; ++j) {
        std::string s;
        std::cin >> s;
        s0.push_back(s);
    }
    for (int i = 1; i < N; i++) {
        std::cin >> M;
        std::unordered_set<std::string> strSet;
        std::string s;
        for (int j = 0; j < M; j++) {   
            std::cin >> s;
            strSet.insert(s);
        }
        for (auto it = strSet.begin(); it != strSet.end(); ++it) {
            mp[*it]++;
        }
    }

    for (int i = 0; i < s0.size(); i++) {
        std::cout << mp[s0[i]] << " ";
    }

    return 0;
}

Qualcuno sa come aiutarmi? :upside_down_face:

Ciao,
leggendo l’input da file (input.txt) e stampando l’output su file (output.txt) il tuo codice prende 100, se inserisci anche le seguenti righe all’inizio del main, che servono a velocizzare l’IO:

std::ios::sync_with_stdio(false);
ifs.tie(0);
#include <bits/stdc++.h>

// input data
int N, L;

int main() {
    std::ifstream ifs("input.txt");
    std::ofstream ofs("output.txt");

    std::ios::sync_with_stdio(false);
    ifs.tie(0);

    std::unordered_map <std::string, int> mp;
    std::vector<std::string> s0;
    ifs >> N >> L;

    int M;
    ifs >> M;
    for (int j = 0; j < M; ++j) {
        std::string s;
        ifs >> s;
        s0.push_back(s);
    }

    for (int i = 1; i < N; i++) {
        ifs >> M;
        std::unordered_set<std::string> strSet;
        std::string s;

        for (int j = 0; j < M; j++) {
            ifs >> s;
            strSet.insert(s);
        }

        for (auto it = strSet.begin(); it != strSet.end(); ++it) {
            mp[*it]++;
        }
    }

    for (size_t i = 0; i < s0.size(); i++) {
        ofs << mp[s0[i]] << " ";
    }

    return 0;
}

Inoltre, al posto di includere ogni libreria che ti serve tutte le volte che risolvi un problema, ti suggerisco di usare <bits/stdc++.h>, che le comprende già tutte.

Con qualche ritocco, oltre a quelli giustamente suggeriti da @guglielmo.boi per la velocizzazione dell’I/O, il tuo codice entra anche in classifica (1,2s. circa).
Il tuo codice attuale carica in mp anche stringhe che non sono presenti in s0, si può evitare.

Grazie mille dei consigli a entrambi, ora termina correttamente tutti i testcase, e lavorerò sull’ottimizzazione suggerita da v.bizzarri :blush:

1 Mi Piace