oj.uz

Submission #884325

# Submission time Handle Problem Language Result Execution time Memory
884325 2023-12-07T06:59:07 Z vjudge1 Lozinke (COCI17_lozinke) C++17
20 / 100
 59 ms 11564 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1;
const int B = 184871427;
const int MOD = 1e9+7;
int add(int x,int y) {return ((x+y>=MOD)?x+y-MOD:x+y);}
int mult(int x,int y) {return ((x%MOD)*(y%MOD))%MOD;}
int expo(int x,int y) {
  if (!y) return 1;
  int e = expo(x,y/2);
  e = mult(e,e);
  if (y&1) e = mult(e,x);
  return e;
}
void solve() {
  int n;
  cin >> n;
  unordered_map<string,int> ss;
  F(i,n) {
    string s;
    cin >> s;
    ss[s]++;
  } 
  int ans = 0;
  for (auto it : ss) ans+=it.second*(it.second-1);
  vector<string> strs = {""};
  for (auto it : ss) strs.push_back(it.first);
  sort(strs.begin(),strs.end(),[](string s,string t){return s.size()<t.size();});
  n = strs.size()-1;
  unordered_map<int,int> occ;
  F(i,n) {
    string s = strs[i];
    int nn = s.size();
    vi hsh(nn+1);
    hsh[0] =0 ;
    for (int i=1;i<=nn;i++) hsh[i] = add(mult(hsh[i-1],B),s[i-1]);
    for (int L=1;L<=nn;L++) {
      for (int R=L;R<=nn;R++) {
        ans+=ss[s]*occ[add(hsh[R],MOD-mult(expo(B,R-L+1),hsh[L-1]))];
      }
    }
    occ[hsh[nn]]+=ss[s];
  }
  cout << ans << endl;
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 452 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 2 ms 604 KB Output isn't correct
6 Incorrect 3 ms 604 KB Output isn't correct
7 Incorrect 4 ms 1116 KB Output isn't correct
8 Correct 6 ms 1624 KB Output is correct
9 Incorrect 15 ms 2252 KB Output isn't correct
10 Correct 27 ms 5852 KB Output is correct
11 Incorrect 25 ms 3796 KB Output isn't correct
12 Incorrect 59 ms 10912 KB Output isn't correct
13 Incorrect 34 ms 3160 KB Output isn't correct
14 Incorrect 51 ms 11564 KB Output isn't correct
15 Correct 52 ms 11424 KB Output is correct
16 Incorrect 6 ms 848 KB Output isn't correct
17 Correct 2 ms 604 KB Output is correct
18 Incorrect 2 ms 604 KB Output isn't correct
19 Incorrect 37 ms 6520 KB Output isn't correct
20 Incorrect 6 ms 860 KB Output isn't correct