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;
}
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.
Stavo provando ad ottimizzare il codice seguendo anche il tuo consiglio(@v.bizzarri) e ho pensato che bastasse verificare che le key presenti nel set lo fossero anche nella map con “if(mp.find(*it)!=mp.end())”, ma così facendo mi da 0/100 in tutti i test case. Qualcuno sa dirmi perchè?
