Submission #97758

#	Time	Username	Problem	Language	Result	Execution time	Memory
97758		dalgerok	Lozinke (COCI17_lozinke)	C++17	100 / 100	805 ms	38340 KiB

lozinke

#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 / 100