Submission #141673

#	Time	Username	Problem	Language	Result	Execution time	Memory
141673		mariadinca	Lozinke (COCI17_lozinke)	C++14	100 / 100	272 ms	2408 KiB

lozinke

#include <iostream>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int n, sol, i, j, k, lung = 1;

string s[20001], secc;
map<string, int> m;
set<string> secv;

int cmp(string a, string b){
    if(a.length() != b.length())
        return a.length() < b.length();
    return a < b;
}

int main(){
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>s[i];          /// parolele
    sort(s+1, s+n+1, cmp);
    /// acum trebuie sa iau fiecare cuvant, sa ii construiesc toate secventele si sa vad daca acele secvente pot debloca parole anterioare
    for(i=1;i<=n;i++){
        secv.clear();       /// asta este setul in care voi pune toate secventele cuvantului curent
        for(j=0;s[i][j]!=0;j++){
            secc.clear();
            for(k=j;s[i][k]!=0;k++){
                secc.push_back(s[i][k]);
                secv.insert(secc);
            }
        }
        for(set<string>:: iterator it = secv.begin(); it!=secv.end(); it++)     /// acum parcurg toate secventele din cuvant si le caut in m
            if(m.find(*it) != m.end())                      /// daca gasesc o secventa inainte de finalul lui m
                sol+=m[*it];
        /// abia acum adaugam cuvantul curent in map
        if(m.find(s[i]) != m.end())
            m[s[i]]++;
        else
            m[s[i]] = 1;
    }
    /// asta ar fi ok daca nu ar exista cuvinte identice
    /// pentru ca, in map, nu se repeta cuvintele
    for(i=2;i<=n;i++){
        if(s[i] == s[i-1])
            lung++;
        else
            lung = 1;
        sol += lung-1;
    }
    cout<<sol;
    return 0;
}

• Subtask 1: 100 / 100