oj.uz

Submission #747760

# Submission time Handle Problem Language Result Execution time Memory
747760 2023-05-24T16:04:58 Z Prieved1 Palindromes (APIO14_palindrome) C++17
100 / 100
 72 ms 73384 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=300000+100;
int sz[N], snext[N];
int child[N][27], cnt[N];
vector<int> g[N];
long long dp[N];
void dfs(int at) {
  dp[at]=cnt[at];
  for(int to:g[at]) {
    if(to==at)continue;
    dfs(to);
    dp[at]+=dp[to];
  }
}
int main () {
  cin.tie(0)->sync_with_stdio(0);
  string s;
  cin >> s;
  int n=s.size();
  int pt=0;
  sz[0]=0;
  sz[1]=-1;
  snext[0]=1;
  snext[1]=1;
  int nodecnt=2;
  for(int i = 0;i<n;i++) {
    int cur=pt;
    while(cur!=1 and ((i-sz[cur]-1)<0 or s[i-sz[cur]-1]!=s[i]))cur=snext[cur];
    int curnode=0;
    if(child[cur][s[i]-'a']!=0) {
      curnode=child[cur][s[i]-'a'];
    }
    else {
      curnode=nodecnt++;
      child[cur][s[i]-'a']=curnode;
    }
    pt=curnode;
    sz[curnode]=sz[cur]+2;
    cnt[pt]++;
    if(cur==1) {
      snext[curnode]=0;
    }
    else {
      cur=snext[cur];
      while(cur!=1 and ((i-sz[cur]-1)<0 or s[i-sz[cur]-1]!=s[i]))cur=snext[cur];
      snext[curnode]=child[cur][s[i]-'a'];
    }
  }
  for(int i = 0;i<=n+2;i++) {
    g[snext[i]].push_back(i);
  }
  dfs(0);
  long long res=0;
  for(int i = 2;i<=n+2;i++) {
    res=max(res, sz[i]*dp[i]);
  }
  cout << res << "\n";
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7312 KB Output is correct
9 Correct 4 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 3 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7332 KB Output is correct
15 Correct 4 ms 7380 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7384 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7388 KB Output is correct
20 Correct 4 ms 7304 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 4 ms 7380 KB Output is correct
23 Correct 4 ms 7380 KB Output is correct
24 Correct 4 ms 7380 KB Output is correct
25 Correct 4 ms 7380 KB Output is correct
26 Correct 4 ms 7380 KB Output is correct
27 Correct 4 ms 7380 KB Output is correct
28 Correct 4 ms 7380 KB Output is correct
29 Correct 4 ms 7380 KB Output is correct
30 Correct 4 ms 7380 KB Output is correct
31 Correct 4 ms 7432 KB Output is correct
32 Correct 4 ms 7380 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7508 KB Output is correct
2 Correct 4 ms 7524 KB Output is correct
3 Correct 3 ms 7508 KB Output is correct
4 Correct 4 ms 7508 KB Output is correct
5 Correct 4 ms 7508 KB Output is correct
6 Correct 4 ms 7508 KB Output is correct
7 Correct 4 ms 7508 KB Output is correct
8 Correct 4 ms 7508 KB Output is correct
9 Correct 4 ms 7508 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7508 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9172 KB Output is correct
2 Correct 5 ms 9140 KB Output is correct
3 Correct 6 ms 9556 KB Output is correct
4 Correct 5 ms 9428 KB Output is correct
5 Correct 5 ms 8788 KB Output is correct
6 Correct 6 ms 8916 KB Output is correct
7 Correct 6 ms 9044 KB Output is correct
8 Correct 4 ms 7636 KB Output is correct
9 Correct 4 ms 7652 KB Output is correct
10 Correct 5 ms 8288 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 26252 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 19 ms 29396 KB Output is correct
4 Correct 20 ms 27064 KB Output is correct
5 Correct 17 ms 21192 KB Output is correct
6 Correct 15 ms 19136 KB Output is correct
7 Correct 18 ms 21536 KB Output is correct
8 Correct 7 ms 8976 KB Output is correct
9 Correct 10 ms 13596 KB Output is correct
10 Correct 17 ms 19284 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 63920 KB Output is correct
2 Correct 42 ms 57168 KB Output is correct
3 Correct 55 ms 73384 KB Output is correct
4 Correct 45 ms 61396 KB Output is correct
5 Correct 72 ms 49656 KB Output is correct
6 Correct 43 ms 52920 KB Output is correct
7 Correct 44 ms 48852 KB Output is correct
8 Correct 16 ms 11600 KB Output is correct
9 Correct 16 ms 11876 KB Output is correct
10 Correct 60 ms 43148 KB Output is correct
11 Correct 50 ms 57940 KB Output is correct
12 Correct 19 ms 17480 KB Output is correct