Submission #444210

#TimeUsernameProblemLanguageResultExecution timeMemory
444210BeanZLozinke (COCI17_lozinke)C++14
95 / 100
297 ms15892 KiB
// I_Love_LPL 1y0m3d #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e5 + 5; long long mod = 2038074751; const int lim = 4e5 + 5; const int lg = 20; const int base = 37; const long double eps = 1e-6; string s[N]; ll h[N], p[N]; map<ll, ll> mem; ll get(ll l, ll r){ return (h[r] - h[l - 1] * p[r - l + 1] + mod * mod) % mod; } bool cmp(string x, string y){ return x.length() < y.length(); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("tests.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n; cin >> n; for (int i = 1; i <= n; i++){ cin >> s[i]; } sort(s + 1, s + n + 1, cmp); p[0] = 1; ll ans = 0; for (int i = 1; i <= 10; i++) p[i] = p[i - 1] * base % mod; for (int i = 1; i <= n; i++){ ll x = s[i].length(); for (int j = 1; j <= x; j++){ h[j] = (h[j - 1] * base + (s[i][j - 1] - 'a' + 1)) % mod; } map<ll, ll> eat; for (int j = 1; j <= x; j++){ for (int k = j; k <= x; k++){ if (j == 1 && k == x) continue; if (!eat[get(j, k)]) ans = ans + mem[get(j, k)]; eat[get(j, k)] = 1; } } mem[h[x]]++; } for (auto j : mem){ ans = ans + j.second * (j.second - 1); } cout << ans; } /* Ans: Out: */

Compilation message (stderr)

lozinke.cpp: In function 'int main()':
lozinke.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...