oj.uz

Submission #97758

# Submission time Handle Problem Language Result Execution time Memory
97758 2019-02-18T10:23:25 Z dalgerok Lozinke (COCI17_lozinke) C++17
100 / 100
 805 ms 38340 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;


struct super_hash{
    size_t operator()(string x)const{
        unsigned long long cur = 0, p = 1;
        for(auto it : x){
            cur += p * it;
            p *= 59;
        }
        return cur;
    }
};

gp_hash_table < string, int >  q;

inline void add(string &s){
    gp_hash_table < string, int >  used;
    for(int i = 0; i < (int)s.size(); i++){
        string t;
        for(int j = i; j < (int)s.size(); j++){
            t += s[j];
            if(used.find(t) == used.end()){
                q[t] += 1;
                used[t] = true;
            }
        }
    }
}
inline void del(string &s){
    gp_hash_table < string, int >  used;
    for(int i = 0; i < (int)s.size(); i++){
        string t;
        for(int j = i; j < (int)s.size(); j++){
            t += s[j];
            if(used.find(t) == used.end()){
                q[t] -= 1;
                used[t] = false;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    string s[n];
    for(int i = 0; i < n; i++){
        cin >> s[i];
        add(s[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        del(s[i]);
        ans += q[s[i]];
        add(s[i]);
    }
    cout << ans;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 27 ms 1656 KB Output is correct
6 Correct 32 ms 1656 KB Output is correct
7 Correct 42 ms 2808 KB Output is correct
8 Correct 66 ms 5216 KB Output is correct
9 Correct 221 ms 5476 KB Output is correct
10 Correct 364 ms 19336 KB Output is correct
11 Correct 313 ms 10340 KB Output is correct
12 Correct 805 ms 38092 KB Output is correct
13 Correct 559 ms 5824 KB Output is correct
14 Correct 543 ms 38340 KB Output is correct
15 Correct 801 ms 38208 KB Output is correct
16 Correct 623 ms 1408 KB Output is correct
17 Correct 236 ms 1144 KB Output is correct
18 Correct 241 ms 1124 KB Output is correct
19 Correct 521 ms 19796 KB Output is correct
20 Correct 293 ms 1408 KB Output is correct