Submission #794667

#	Time	Username	Problem	Language	Result	Execution time	Memory
794667		cig32	Palindromes (APIO14_palindrome)	C++17	100 / 100	62 ms	50908 KiB

palindrome

#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 << ": "; }
struct pam {
  vector<vector<int>>pam;
  vector<vector<int>>revfail;
  vector<int> oddrt,evenrt,fail,len,alleq,corr;
  string s;//the string itself
  // Declare other variables here
  vector<int> dp;
  void init(int n) {
    pam.resize(n + 5);
    revfail.resize(n + 5);
    fail.resize(n + 5);
    len.resize(n + 5);
    alleq.resize(n + 5);
    corr.resize(n + 5);
    // Initialize other arrays here
    dp.resize(n + 5);
  }
  void append(char c) {
    int i = s.size();
    s += c;
    if(i == 0) {
      fail[0] = -1;
      len[0] = 1;
      dp[0] = 1;
      alleq[0] = 1;
      corr[0] = 0;
      oddrt.push_back(0);
      return;
    }
    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)return;
      fail[i] = -1;
      len[i] = 1;
      alleq[i] = 1;
      dp[i] = 1;
      corr[i] = i;
      oddrt.push_back(i);
    }
  }
  void compile() { // MUST COMPILE BEFORE ANY QUERY
    for(int i=0;i<s.size();i++){
      if(len[i]==2)evenrt.push_back(i);
    }
  }
  public:
  int ans = 0;
  void dfs(int node) {
    for(int x: revfail[node]) {
      dfs(x);
      dp[node] += dp[x];
    }
    ans = max(ans, dp[node] * len[node]); 
  }
  int solve() {
    for(int x: oddrt) dfs(x);
    return ans;
  }
};
void solve(int tc) {
  string s;
  cin>>s;
  pam bruh;
  bruh.init(s.size());
  for(char c:s) bruh.append(c);
  bruh.compile();
  cout<<bruh.solve()<<"\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 (stderr)

palindrome.cpp: In member function 'void pam::compile()':
palindrome.cpp:146:18: 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]
  146 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27