#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"
template<class T> ostream& operator<< (ostream& out, vector<T> v) {
out << '[';
for (int i = 0; i < v.size(); ++i) {
if (i > 0) {
out << ", ";
}
out << v[i];
}
return out << ']';
}
template<class T> ostream& operator<< (ostream& out, set<T> v) {
return out << vector<T>(v.begin(), v.end());
}
template<class A, unsigned int sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
out << '[';
for (int i = 0; i < sz; ++i) {
if (i > 0) out << ", ";
out << a[i];
}
return out << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
return out << '[' << p.first << ", " << p.second << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, map<A, B> mp) {
return out << vector<pair<A, B>>(mp.begin(), mp.end());
}
const unsigned long long SEED = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
const int M=1e9+7;
uniform_int_distribution<int> BDIST(0.1*M, 0.9*M);
const int B=BDIST(rng);
int n;
ll ans;
map<string, int> oc[11];
map<int, int> mp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=0; i<n; ++i) {
string s;
cin >> s;
++oc[s.size()][s];
}
for (int i=1; i<=10; ++i) {
for (auto& x : oc[i]) {
set<int> st;
string s=x.first;
int cnt=x.second;
ans+=(ll)cnt*(cnt-1);
//cout << s << " " << cnt << endl;
//debug(s);
for (int i=0; i<s.size(); ++i) {
ll hsh=0;
for (int j=i; j<s.size(); ++j) {
hsh=(B*hsh+s[j])%M;
st.insert(hsh);
}
}
//debug(mp);
//debug(st);
for (const int& j : st) {
if (mp.count(j)) {
ans+=(ll)cnt*mp[j];
//cout << s << " " << cnt << " " << mp[j] << endl;
}
}
//debug(ans);
ll hsh=0;
for (char c : s)
hsh=(B*hsh+c)%M;
mp[hsh]+=cnt;
}
}
cout << ans;
return 0;
}
Compilation message
lozinke.cpp: In function 'int main()':
lozinke.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i=0; i<s.size(); ++i) {
| ~^~~~~~~~~
lozinke.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int j=i; j<s.size(); ++j) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
2 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
8 ms |
472 KB |
Output is correct |
| 7 |
Correct |
11 ms |
496 KB |
Output is correct |
| 8 |
Correct |
9 ms |
460 KB |
Output is correct |
| 9 |
Correct |
47 ms |
1044 KB |
Output is correct |
| 10 |
Correct |
55 ms |
1092 KB |
Output is correct |
| 11 |
Incorrect |
73 ms |
1448 KB |
Output isn't correct |
| 12 |
Incorrect |
91 ms |
1536 KB |
Output isn't correct |
| 13 |
Correct |
106 ms |
2016 KB |
Output is correct |
| 14 |
Incorrect |
134 ms |
2272 KB |
Output isn't correct |
| 15 |
Incorrect |
177 ms |
1848 KB |
Output isn't correct |
| 16 |
Correct |
18 ms |
460 KB |
Output is correct |
| 17 |
Correct |
4 ms |
204 KB |
Output is correct |
| 18 |
Correct |
3 ms |
204 KB |
Output is correct |
| 19 |
Incorrect |
86 ms |
1796 KB |
Output isn't correct |
| 20 |
Correct |
17 ms |
460 KB |
Output is correct |
