oj.uz

Submission #157646

# Submission time Handle Problem Language Result Execution time Memory
157646 2019-10-12T16:31:19 Z sadmanrizwan Palindromes (APIO14_palindrome) C++14
0 / 100
 92 ms 45212 KB 
#include <bits/stdc++.h>
using namespace std;
const int MX=300005;
struct node{
    int len,link,cnt;
    map <char,int> to;
};
node pt[MX];
int size,last;
char s[MX];
vector <int> idx[MX];
void init_node(int n)
{
    pt[n].len=0;
    pt[n].cnt=0;
    pt[n].link=-1;
    pt[n].to.clear();
}
void init_pt()
{
    init_node(0);
    init_node(1);
    pt[0].len=pt[0].link=-1;
    pt[1].link=0;
    size=2,last=1;
}
int find(int n,char s[],int i)
{
    while(n){
        int j=i-pt[n].len-1;
        if(j>=0 && s[i]==s[j]) return n;
        n=pt[n].link;
    }
    return n;
}
void extend(char s[],int i)
{
    int n=find(last,s,i);
    if(pt[n].to.count(s[i])==0){
        int m=size++;
        init_node(m);
        pt[n].to[s[i]]=m;
        pt[m].len=pt[n].len+2;
        if(pt[m].len==1) pt[m].link=1;
        else{
            int v=find(pt[n].link,s,i);
            pt[m].link=pt[v].to[s[i]];
        }
        last=m;
    }
    else last=pt[n].to[s[i]];
}
int main()
{
    scanf("%s",s);
    int n=strlen(s);
    init_pt();
    for(int i=0;i<n;i++){
        extend(s,i);
        pt[last].cnt++;
        idx[pt[last].len].push_back(last);
    }
    for(int i=n;i>0;i--){
        int l=idx[i].size();
        for(int j=0;j<l;j++){
            int v=idx[i][j];
            int u=pt[v].link;
            if(u>1) pt[u].cnt+=pt[v].cnt;
        }
    }
    int ans=0;
    for(int i=2;i<size;i++){
        ans=max(ans,pt[i].cnt*pt[i].len);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 26104 KB Output is correct
2 Correct 25 ms 26104 KB Output is correct
3 Correct 25 ms 26104 KB Output is correct
4 Correct 23 ms 26104 KB Output is correct
5 Correct 26 ms 26176 KB Output is correct
6 Correct 25 ms 26104 KB Output is correct
7 Correct 25 ms 26104 KB Output is correct
8 Correct 25 ms 26104 KB Output is correct
9 Correct 31 ms 26104 KB Output is correct
10 Correct 26 ms 26104 KB Output is correct
11 Incorrect 25 ms 26104 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 26232 KB Output is correct
2 Correct 25 ms 26232 KB Output is correct
3 Correct 25 ms 26272 KB Output is correct
4 Correct 25 ms 26232 KB Output is correct
5 Correct 26 ms 26232 KB Output is correct
6 Correct 25 ms 26236 KB Output is correct
7 Correct 25 ms 26236 KB Output is correct
8 Correct 26 ms 26232 KB Output is correct
9 Incorrect 26 ms 26160 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 26716 KB Output is correct
2 Correct 28 ms 26744 KB Output is correct
3 Correct 28 ms 26988 KB Output is correct
4 Correct 28 ms 26872 KB Output is correct
5 Correct 27 ms 26748 KB Output is correct
6 Correct 27 ms 26744 KB Output is correct
7 Correct 27 ms 26744 KB Output is correct
8 Incorrect 26 ms 26224 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 32564 KB Output is correct
2 Correct 44 ms 31964 KB Output is correct
3 Incorrect 48 ms 34224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 45212 KB Output isn't correct
2 Halted 0 ms 0 KB -