oj.uz

Submission #155262

# Submission time Handle Problem Language Result Execution time Memory
155262 2019-09-27T11:28:38 Z BrehamPie Palindromes (APIO14_palindrome) C++14
100 / 100
 68 ms 37492 KB 
#include<bits/stdc++.h>
#define FastIO      ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0)
#define pb          push_back
#define siz         100009
#define inf         1e9+8
#define mp          make_pair
#define rep(i,n)    for(int i=0;i<n;i++)
#define repo(i,m,n) for(int i=m;i<=n;i++)
#define ll          long long
#define pii         pair<int,int >
#define sc(n)       scanf("%d",&n)
#define sc2(m,n)    scanf("%d%d",&m,&n);
#define MOD         4294967296
#define fileout     freopen("output.txt","w",stdout)
#define filein      freopen("input.txt","r",stdin)
#define mem(x,i)    memset(x,i,sizeof x)
#define PI          acos(-1.0)
#define ff          first
#define ss          second
#define all(x)      x.begin(),x.end()
#define Case(t)     for(int ks=1;ks<=t;ks++)
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
const int N=3e5+10;
int tree[N][26],idx;
ll len[N];int link[N];
int ans[N],occ[N];
int t;
string str;
void extend(int p)
{
    while(str[p-len[t]-1]!=str[p])
        t=link[t];
    int x=link[t],c=str[p]-'a';
    while(str[p-len[x]-1]!=str[p])
        x=link[x];
    if(!tree[t][c])
    {
        tree[t][c]=++idx;
        len[idx]=len[t]+2;
        link[idx]=(len[idx]==1?2:tree[x][c]);
        ans[idx]=1+ans[link[idx]];
    }
    t=tree[t][c];
    ++occ[t];
}
int main()
{

    {
        mem(tree,0);
        len[1]=-1;
        len[2]=0;
        link[1]=link[2]=1;
        idx=t=2;
        cin>>str;
        str=' '+str;
        int n=str.size();
        ll val=0;
        for(int i=1; i<str.size(); i++)
        {
            extend(i);
            //val+=ans[t];
        }
        for(int i=idx;i>2;i--) occ[link[i]]+=occ[i];
        for(int i=3;i<=idx;i++)val=max(val,occ[i]*len[i]);
        printf("%lld\n",val);
    }
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1; i<str.size(); i++)
                      ~^~~~~~~~~~~
palindrome.cpp:65:13: warning: unused variable 'n' [-Wunused-variable]
         int n=str.size();
             ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 30840 KB Output is correct
2 Correct 27 ms 30812 KB Output is correct
3 Correct 27 ms 30916 KB Output is correct
4 Correct 27 ms 30840 KB Output is correct
5 Correct 27 ms 30844 KB Output is correct
6 Correct 27 ms 30940 KB Output is correct
7 Correct 27 ms 30840 KB Output is correct
8 Correct 27 ms 30840 KB Output is correct
9 Correct 26 ms 30840 KB Output is correct
10 Correct 26 ms 30840 KB Output is correct
11 Correct 27 ms 30840 KB Output is correct
12 Correct 27 ms 30896 KB Output is correct
13 Correct 27 ms 30840 KB Output is correct
14 Correct 34 ms 30912 KB Output is correct
15 Correct 30 ms 30904 KB Output is correct
16 Correct 29 ms 30744 KB Output is correct
17 Correct 27 ms 30840 KB Output is correct
18 Correct 27 ms 30840 KB Output is correct
19 Correct 27 ms 30840 KB Output is correct
20 Correct 27 ms 30840 KB Output is correct
21 Correct 27 ms 30840 KB Output is correct
22 Correct 27 ms 30880 KB Output is correct
23 Correct 27 ms 30812 KB Output is correct
24 Correct 27 ms 30968 KB Output is correct
25 Correct 27 ms 30840 KB Output is correct
26 Correct 27 ms 30840 KB Output is correct
27 Correct 24 ms 30840 KB Output is correct
28 Correct 27 ms 30840 KB Output is correct
29 Correct 27 ms 30840 KB Output is correct
30 Correct 27 ms 30840 KB Output is correct
31 Correct 29 ms 30824 KB Output is correct
32 Correct 27 ms 30840 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 30840 KB Output is correct
2 Correct 27 ms 30940 KB Output is correct
3 Correct 27 ms 31016 KB Output is correct
4 Correct 27 ms 30968 KB Output is correct
5 Correct 31 ms 30968 KB Output is correct
6 Correct 27 ms 30844 KB Output is correct
7 Correct 31 ms 30968 KB Output is correct
8 Correct 29 ms 30968 KB Output is correct
9 Correct 28 ms 30968 KB Output is correct
10 Correct 28 ms 30832 KB Output is correct
11 Correct 27 ms 30840 KB Output is correct
12 Correct 32 ms 30940 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 31096 KB Output is correct
2 Correct 28 ms 31096 KB Output is correct
3 Correct 28 ms 31068 KB Output is correct
4 Correct 28 ms 31096 KB Output is correct
5 Correct 28 ms 31096 KB Output is correct
6 Correct 28 ms 31096 KB Output is correct
7 Correct 28 ms 31068 KB Output is correct
8 Correct 28 ms 30968 KB Output is correct
9 Correct 27 ms 30968 KB Output is correct
10 Correct 28 ms 31096 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 33012 KB Output is correct
2 Correct 36 ms 33012 KB Output is correct
3 Correct 36 ms 33012 KB Output is correct
4 Correct 36 ms 33012 KB Output is correct
5 Correct 36 ms 33012 KB Output is correct
6 Correct 36 ms 32500 KB Output is correct
7 Correct 36 ms 32740 KB Output is correct
8 Correct 34 ms 31096 KB Output is correct
9 Correct 35 ms 31476 KB Output is correct
10 Correct 41 ms 32756 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 37076 KB Output is correct
2 Correct 60 ms 37492 KB Output is correct
3 Correct 63 ms 37448 KB Output is correct
4 Correct 64 ms 37484 KB Output is correct
5 Correct 68 ms 37428 KB Output is correct
6 Correct 61 ms 36844 KB Output is correct
7 Correct 63 ms 36456 KB Output is correct
8 Correct 55 ms 31892 KB Output is correct
9 Correct 58 ms 31892 KB Output is correct
10 Correct 61 ms 36348 KB Output is correct
11 Correct 63 ms 37480 KB Output is correct
12 Correct 51 ms 32204 KB Output is correct