oj.uz

Submission #99956

# Submission time Handle Problem Language Result Execution time Memory
99956 2019-03-09T01:29:14 Z Ramprosad Palindromes (APIO14_palindrome) C++14
100 / 100
 66 ms 35220 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll             long long
#define LL             long long
#define gcd(a,b)       __gcd(a, b)
#define lcm(a,b)       a * (b / gcd(a, b))
#define pii            pair<int, int>
#define pll            pair<ll, ll>
#define pil            pair<int, ll>
#define pli            pair<ll, int>
#define vi             vector<int>
#define vl             vector<ll>
#define vii            vector<pii>
#define vll            vector<pll>
#define vil            vector<pil>
#define vli            vector<pli>
#define pb             push_back
#define ppb            pop_back
#define mp             make_pair
#define ff             first
#define ss             second
#define all(v)         v.begin(), v.end()
#define fill(a, b)     memset(a, b, sizeof a)
#define smax(a, b)     a = max(a, b)
#define smin(a, b)     a = min(a, b)
#define sqr(x)         x * x
#define cube(x)        x * x * x
#define endl           '\n'

int in() {
    int n;
    scanf("%d", &n);
    return n;
}

ll Lin() {
    ll n;
    scanf("%lld", &n);
    return n;
}

double Din() {
    double n;
    scanf("%lf", &n);
    return n;
}

const ll inf = (ll)1e17;
const ll mod = (ll)1e9 + 7;
const int N = 3e5 + 5;

int tree[N][26], len[N], link[N], occ[N], node, t;

string s;

void add(int p){
    while(p - len[t] - 1 < 0 || s[p - len[t] - 1] != s[p]) t = link[t];
    int x = link[t], c = s[p] - 'a';
    while(p - len[x] - 1 < 0 || s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][c]) {
        tree[t][c] = ++node;
        len[node] = len[t] + 2;
        link[node] = len[node] == 1 ? 2 : tree[x][c];
    }
    t = tree[t][c];
}

void buildPT() {
    len[1] = -1, len[2] = 0;
    link[1] = link[2] = 1;
    node = t = 2;
    int n = s.size();
    for(int i = 0; i < n; i++){
        add(i);
        occ[t]++;
    }
    ll ans = 0LL;
    for(int i = node; i > 2; i--){
        occ[link[i]] += occ[i];
        smax(ans, (ll)occ[i] * len[i]);
    }
    printf("%lld\n", ans);
}

int solve() {
    cin >> s;
    buildPT();
    return 0;
}

int main() {
    int test = 1, tc = 0;
    while(test--) {
        //printf("Case %d:\n", ++tc);
        solve();
    }
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:93:19: warning: unused variable 'tc' [-Wunused-variable]
     int test = 1, tc = 0;
                   ^~
palindrome.cpp: In function 'int in()':
palindrome.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
palindrome.cpp: In function 'long long int Lin()':
palindrome.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'double Din()':
palindrome.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lf", &n);
     ~~~~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1536 KB Output is correct
2 Correct 4 ms 1536 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 5 ms 1536 KB Output is correct
5 Correct 3 ms 1536 KB Output is correct
6 Correct 3 ms 1536 KB Output is correct
7 Correct 4 ms 1536 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 1152 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 12032 KB Output is correct
2 Correct 18 ms 12032 KB Output is correct
3 Correct 21 ms 12032 KB Output is correct
4 Correct 18 ms 12024 KB Output is correct
5 Correct 23 ms 11948 KB Output is correct
6 Correct 15 ms 8960 KB Output is correct
7 Correct 17 ms 10240 KB Output is correct
8 Correct 8 ms 808 KB Output is correct
9 Correct 9 ms 3328 KB Output is correct
10 Correct 20 ms 10240 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 35064 KB Output is correct
2 Correct 60 ms 35120 KB Output is correct
3 Correct 50 ms 35220 KB Output is correct
4 Correct 55 ms 35092 KB Output is correct
5 Correct 66 ms 35092 KB Output is correct
6 Correct 45 ms 31256 KB Output is correct
7 Correct 50 ms 29332 KB Output is correct
8 Correct 18 ms 1308 KB Output is correct
9 Correct 16 ms 1308 KB Output is correct
10 Correct 51 ms 28948 KB Output is correct
11 Correct 48 ms 35220 KB Output is correct
12 Correct 25 ms 4372 KB Output is correct