oj.uz

Submission #99290

# Submission time Handle Problem Language Result Execution time Memory
99290 2019-03-02T08:26:45 Z mirbek01 Palindromes (APIO14_palindrome) C++11
0 / 100
 1000 ms 100524 KB 
# include <bits/stdc++.h>

using namespace std;

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

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

int get(int l, int r){
      long long hs = (h[r] - h[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
int get1(int l, int r){
      long long hs = (h1[r] - h1[l - 1] + mod) % mod;
      hs = (hs * pw[N - l]) % mod;
      return hs;
}
void add(int v, int id, int len, int c){
      while(1){
            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;
            len ++;
      }
      cnt[v] ++;
}
void f(int v, int len, int c){
      for(int i = 0; i < 26; i ++){
            if(bor[i][v]){
                  t += char('a' + i);
                  f(bor[i][v], len + 1, c);
                  cnt[v] += cnt[bor[i][v]];
                  t.pop_back();
            }
      }
      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;
            h1[i] = (h1[i - 1] + (s[n - i + 1] - '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;
                  int f = get(md, i + (i - md)), s = get1(n - (i + (i - md)) + 1, n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        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;
                  int f = get(md, i + (i - md) + 1), s = get1(n - (i + (i - md) + 1), n - md + 1);
                  if(mp[get(md, i)] && f == s)
                        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:92: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:67: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 54 ms 64888 KB Output is correct
2 Incorrect 53 ms 64888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 65016 KB Output is correct
2 Correct 54 ms 65092 KB Output is correct
3 Correct 65 ms 64988 KB Output is correct
4 Correct 57 ms 65144 KB Output is correct
5 Correct 58 ms 65124 KB Output is correct
6 Incorrect 55 ms 65144 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 65912 KB Output is correct
2 Correct 67 ms 66732 KB Output is correct
3 Incorrect 64 ms 65804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 75368 KB Output is correct
2 Correct 364 ms 80280 KB Output is correct
3 Correct 285 ms 73512 KB Output is correct
4 Correct 346 ms 76980 KB Output is correct
5 Correct 872 ms 100524 KB Output is correct
6 Correct 876 ms 95672 KB Output is correct
7 Incorrect 815 ms 93160 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 24176 KB Time limit exceeded
2 Halted 0 ms 0 KB -