Submission #725269

#	Time	Username	Problem	Language	Result	Execution time	Memory
725269		quiet_space	회문 (APIO14_palindrome)	C++14	100 / 100	63 ms	65496 KiB

palindrome

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
const int maxn = 300005;
char c[maxn];
int tot, lst, trans[maxn][26], len[maxn], fail[maxn], cnt[maxn];
inline int newnode (int l) {
  len[++ tot] = l; return tot;
}
inline void prework (void) {
  tot = -1; fail[0] = 1;
  newnode (0); newnode (-1);
}
inline int getfail (int x, int pos) {
  while(c[pos] != c[pos - len[x] - 1]) x = fail[x];
  return x;
}
inline void insert (int pos) {
  int x = getfail (lst, pos);
  if(!trans[x][c[pos] - 'a']) {
    int y = newnode (len[x] + 2);
    fail[y] = trans[getfail (fail[x], pos)][c[pos] - 'a'];
    trans[x][c[pos] - 'a'] = y;
  } lst = trans[x][c[pos] - 'a'];
}
std::vector <int> v[maxn];
ll ans;
void dfs (int x) {
  for(auto&it:v[x]) {
    dfs (it);
    cnt[x] += cnt[it];
  }
  if(len[x] > 0) ans = std::max(ans, 1ll * len[x] * cnt[x]);
}
int main (void) {
  scanf("%s", c+1);
  int n = strlen(c+1);
  prework ();
  FOR(i,1,n) {
    insert (i);
    ++ cnt[lst];
  }
  FOR(i,2,tot) v[fail[i]].push_back(i);
  dfs (0); dfs (1);
  printf("%lld\n", ans);
  return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%s", c+1);
      |   ~~~~~^~~~~~~~~~~

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