Submission #373065

#	Time	Username	Problem	Language	Result	Execution time	Memory
373065		Atill83	Lozinke (COCI17_lozinke)	C++14	100 / 100	150 ms	18228 KiB

lozinke

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
#define int long long
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 100000000861;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
string s[MAXN];
int pw[MAXN];
int hsh[MAXN];


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>s[i];
    }
    
    ll ans = 0;

    unordered_map<int, int> mp;

    const int base = 37;

    for(int i = 0; i < n; i++){
        vector<int> vc;
        for(int x = 0; x < s[i].length(); x++){
            int bas = 1;
            int hash = 0;
            for(int y = x; y < s[i].length(); y++){
                hash = (hash + 1LL * bas * (s[i][y] - 'a' + 1) % mod) % mod;
                vc.push_back(hash);
                bas = 1LL * bas * base % mod;
            }
            if(x == 0)
                hsh[i] = hash;
        }
        sort(vc.begin(), vc.end());
        vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
        for(auto u: vc)
            mp[u]++;
    }

    for(int i = 0; i < n; i++){
        ans += mp[hsh[i]] - 1;
    }
    
    cout<<ans<<endl;


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message (stderr)

lozinke.cpp: In function 'int32_t main()':
lozinke.cpp:43:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int x = 0; x < s[i].length(); x++){
      |                        ~~^~~~~~~~~~~~~~~
lozinke.cpp:46:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int y = x; y < s[i].length(); y++){
      |                            ~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100