oj.uz

Submission #794653

# Submission time Handle Problem Language Result Execution time Memory
794653 2023-07-26T18:31:55 Z cig32 Palindromes (APIO14_palindrome) C++17
100 / 100
 59 ms 52156 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
vector<int> pam[MAXN]; // palindromic automaton
vector<int> revfail[MAXN]; // reverse fail edges
vector<int>oddrt;
int fail[MAXN], len[MAXN], alleq[MAXN];//length=length of maximum suffix palindrome
int dp[MAXN], ans = 0;
int corr[MAXN];
void dfs(int node) {
  for(int x: revfail[node]) {
    dfs(x);
    dp[node] += dp[x];
  }
  ans = max(ans, dp[node] * len[node]); 
}
void solve(int tc) {
  string s;
  cin>>s;
  fail[0] = -1;
  len[0] = 1;
  dp[0] = 1;
  alleq[0] = 1;
  corr[0] = 0;
  oddrt.push_back(0);
  for(int i=1;i<s.size();i++){
    int nxt=corr[i-1];
    while(nxt!=-1){
      if(alleq[nxt] && s[i]==s[i-1]) {
        bool done=0;
        for(int x:revfail[nxt]){
          if(s[x]==s[i] && len[x]==len[nxt]+1){
            dp[x]++;
            corr[i]=x;
            done = 1; 
            break;
          }
        }
        if(done) break;
        fail[i]=nxt;
        revfail[nxt].push_back(i);
        len[i]=len[nxt]+1;
        alleq[i]=1;
        dp[i]=1;
        corr[i]=i;
        break;
      }
      if(i-len[nxt]-1>=0 && s[i]==s[i-len[nxt]-1]) {
        bool done=0;
        for(int x:pam[nxt]){
          if(s[x]==s[i]){
            done=1;
            dp[x]++;
            corr[i]=x;
            break;
          }
        }
        if(done)break;
        pam[nxt].push_back(i);
        corr[i]=i;
        dp[i]=1;
        len[i]=len[nxt]+2;
        alleq[i]=alleq[nxt]&(s[i]==s[i-1]);
        int again=nxt;
        fail[i]=-1;
        while(fail[again]!=-1){
          again=fail[again];
          if(i-len[again]-1>=0 && s[i-len[again]-1]==s[i]){
            for(int x:pam[again]){
              if(s[x]==s[i]&&len[x]==len[again]+2){
                fail[i]=x;
                revfail[x].push_back(i);
                break;
              }
            }
            break;
          }
          if(alleq[again] && s[i]==s[i-1]){
            for(int x:revfail[again]){
              if(s[x]==s[i]&&len[x]==len[again]+1){
                fail[i]=x;
                revfail[x].push_back(i);
                break;
              }
            }
            break;
          }
        }
        if(fail[i]==-1){
          for(int x:oddrt){
            if(s[x]==s[i]){
              fail[i]=x;
              revfail[x].push_back(i);
              break;
            }
          }
        }
        break;
      }
      else nxt=fail[nxt];
    }
    if(nxt==-1){//single character
      bool done=0;
      for(int x: oddrt){
        if(s[x]==s[i]){
          dp[x]++;
          corr[i]=x;
          done= 1;break;
        }
      }
      if(done)continue;
      fail[i] = -1;
      len[i] = 1;
      alleq[i] = 1;
      dp[i] = 1;
      corr[i] = i;
      oddrt.push_back(i);
    }
  }
  /*
  for(int i=0;i<s.size();i++)cout<<fail[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<dp[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<len[i]<<" ";
  cout<<"\n";
  for(int i=0;i<s.size();i++)cout<<alleq[i]<<" ";
  cout<<"\n";
  */
  for(int x: oddrt) dfs(x);
  cout<<ans<<"\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Compilation message

palindrome.cpp: In function 'void solve(long long int)':
palindrome.cpp:45:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=1;i<s.size();i++){
      |               ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14404 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 8 ms 14448 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 7 ms 14452 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 7 ms 14416 KB Output is correct
12 Correct 7 ms 14416 KB Output is correct
13 Correct 7 ms 14420 KB Output is correct
14 Correct 7 ms 14424 KB Output is correct
15 Correct 7 ms 14420 KB Output is correct
16 Correct 7 ms 14420 KB Output is correct
17 Correct 7 ms 14368 KB Output is correct
18 Correct 7 ms 14416 KB Output is correct
19 Correct 7 ms 14416 KB Output is correct
20 Correct 7 ms 14416 KB Output is correct
21 Correct 7 ms 14408 KB Output is correct
22 Correct 7 ms 14420 KB Output is correct
23 Correct 9 ms 14420 KB Output is correct
24 Correct 9 ms 14420 KB Output is correct
25 Correct 7 ms 14416 KB Output is correct
26 Correct 7 ms 14420 KB Output is correct
27 Correct 7 ms 14460 KB Output is correct
28 Correct 7 ms 14456 KB Output is correct
29 Correct 7 ms 14424 KB Output is correct
30 Correct 7 ms 14420 KB Output is correct
31 Correct 7 ms 14420 KB Output is correct
32 Correct 7 ms 14420 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14548 KB Output is correct
2 Correct 7 ms 14500 KB Output is correct
3 Correct 8 ms 14560 KB Output is correct
4 Correct 8 ms 14544 KB Output is correct
5 Correct 8 ms 14440 KB Output is correct
6 Correct 7 ms 14548 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14548 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 7 ms 14420 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15572 KB Output is correct
2 Correct 8 ms 15572 KB Output is correct
3 Correct 8 ms 15556 KB Output is correct
4 Correct 8 ms 15444 KB Output is correct
5 Correct 8 ms 15300 KB Output is correct
6 Correct 10 ms 15316 KB Output is correct
7 Correct 8 ms 15444 KB Output is correct
8 Correct 7 ms 14804 KB Output is correct
9 Correct 7 ms 14804 KB Output is correct
10 Correct 8 ms 15060 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 26992 KB Output is correct
2 Correct 20 ms 25952 KB Output is correct
3 Correct 17 ms 26232 KB Output is correct
4 Correct 16 ms 24576 KB Output is correct
5 Correct 20 ms 22996 KB Output is correct
6 Correct 21 ms 22052 KB Output is correct
7 Correct 16 ms 22400 KB Output is correct
8 Correct 13 ms 18204 KB Output is correct
9 Correct 13 ms 20172 KB Output is correct
10 Correct 18 ms 21944 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 52156 KB Output is correct
2 Correct 43 ms 47196 KB Output is correct
3 Correct 34 ms 49848 KB Output is correct
4 Correct 31 ms 40904 KB Output is correct
5 Correct 59 ms 41096 KB Output is correct
6 Correct 39 ms 41624 KB Output is correct
7 Correct 33 ms 37596 KB Output is correct
8 Correct 19 ms 24432 KB Output is correct
9 Correct 18 ms 24272 KB Output is correct
10 Correct 45 ms 36680 KB Output is correct
11 Correct 47 ms 47520 KB Output is correct
12 Correct 19 ms 26836 KB Output is correct