oj.uz

Submission #141673

# Submission time Handle Problem Language Result Execution time Memory
141673 2019-08-08T19:05:22 Z mariadinca Lozinke (COCI17_lozinke) C++14
100 / 100
 272 ms 2408 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 4 ms 1016 KB Output is correct
5 Correct 12 ms 1016 KB Output is correct
6 Correct 17 ms 1016 KB Output is correct
7 Correct 21 ms 1144 KB Output is correct
8 Correct 25 ms 1144 KB Output is correct
9 Correct 95 ms 1528 KB Output is correct
10 Correct 129 ms 1764 KB Output is correct
11 Correct 158 ms 1776 KB Output is correct
12 Correct 246 ms 1880 KB Output is correct
13 Correct 245 ms 2084 KB Output is correct
14 Correct 212 ms 2408 KB Output is correct
15 Correct 272 ms 2192 KB Output is correct
16 Correct 195 ms 1272 KB Output is correct
17 Correct 78 ms 1196 KB Output is correct
18 Correct 62 ms 1144 KB Output is correct
19 Correct 215 ms 2040 KB Output is correct
20 Correct 129 ms 1272 KB Output is correct