oj.uz

Submission #99223

# Submission time Handle Problem Language Result Execution time Memory
99223 2019-03-01T18:29:15 Z mirbek01 Palindromes (APIO14_palindrome) C++11
0 / 100
 912 ms 132096 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 2;
const int mod = 1e9 + 7;

int n, bor[26][N], cnt[N * 27], used[26], cn = 1;
long long ans, h[N], pr = 997, pw[N];
string s;
unordered_map <int, int> mp;

int get(int l, int r){
      long long hs = (h[r] - h[l] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
void add(int v, int id, int len, int c){
      for(; len < min(n - id + 1, id); len ++){
            if(id - len <= 0 || id + len + c > n || s[id - len] != s[id + len + c]){
                  break;
            }
            int now = s[id - len] - 'a';
            if(!bor[now][v]){
                  bor[now][v] = ++ cn;
            }
            v = bor[now][v];
            mp[get(id - len, id)] = v;
      }
      cnt[v] ++;
}
void f(int v, int len, int c){
      for(int i = 0; i < 26; i ++){
            if(bor[i][v]){
                  f(bor[i][v], len + 1, c);
                  cnt[v] += cnt[bor[i][v]];
            }
      }
      ans = max(ans, (len * 2 - c) * 1ll * cnt[v]);
}

int main(){
      cin >> s;
      n = s.size();
      s = ' ' + s;
      pw[0] = pr;
      for(int i = 1; i < N; i ++)
            pw[i] = (pw[i - 1] * pr) % mod;
      for(int i = 1; i <= n; i ++){
            h[i] = (h[i - 1] + (s[i] - 'a' + 1) * pw[i]) % mod;
      }
      for(int i = 1; i <= n; i ++){
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 0);
                  continue;
            }
            int lo = max(1, i - (n - i)), hi = i, pos;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(mp[get(md, i)])
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 0);
      }
      f(1, 0, 1);
      memset(bor, 0, sizeof(bor));
      memset(cnt, 0, sizeof(cnt));
      memset(used, 0, sizeof(used));
      cn = 1;
      mp.clear();
      for(int i = 1; i < n; i ++){
            if(s[i] != s[i + 1])
                  continue;
            if(!used[s[i] - 'a']){
                  used[s[i] - 'a'] = 1;
                  add(1, i, 0, 1);
                  continue;
            }
            int lo = max(1, i - (n - i - 1)), hi = i, pos;
            while(lo <= hi){
                  int md = (lo + hi) >> 1;
                  if(mp[get(md, i)])
                        hi = md - 1, pos = md;
                  else
                        lo = md + 1;
            }
            add(mp[get(pos, i)], i, i - pos + 1, 1);
      }
      f(1, 0, 0);
      cout << ans << endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
       hs = (hs * pw[N - l]) % mod;
                     ~~^~~
palindrome.cpp:82:55: note: 'pos' was declared here
             int lo = max(1, i - (n - i - 1)), hi = i, pos;
                                                       ^~~
palindrome.cpp:15:23: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
       hs = (hs * pw[N - l]) % mod;
                     ~~^~~
palindrome.cpp:58:51: note: 'pos' was declared here
             int lo = max(1, i - (n - i)), hi = i, pos;
                                                   ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 64888 KB Output is correct
2 Correct 59 ms 65016 KB Output is correct
3 Correct 63 ms 64888 KB Output is correct
4 Correct 55 ms 64888 KB Output is correct
5 Correct 59 ms 64944 KB Output is correct
6 Correct 56 ms 64888 KB Output is correct
7 Correct 69 ms 64888 KB Output is correct
8 Correct 54 ms 64888 KB Output is correct
9 Correct 57 ms 64888 KB Output is correct
10 Incorrect 56 ms 64888 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 64976 KB Output is correct
2 Incorrect 64 ms 65016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 65656 KB Output is correct
2 Incorrect 72 ms 66628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 72988 KB Output is correct
2 Incorrect 368 ms 78980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 912 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -