oj.uz

Submission #392759

# Submission time Handle Problem Language Result Execution time Memory
392759 2021-04-21T15:11:34 Z danielcm585 Palindromes (APIO14_palindrome) C++14
100 / 100
 82 ms 73588 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> ii;

const int N = 3e5;
ll suff, num, ans;
string s;

struct node {
    int nx[26];
    ll link, len, cnt;
    vector<int> adj;
    
} tree[N+2];

void insert(int p) {
    int curSuff = suff, curLen = 0, x = s[p]-'a';
    while (1) {
        curLen = tree[curSuff].len;
        if (p-1-curLen >= 0 && s[p-1-curLen] == s[p]) break;
        curSuff = tree[curSuff].link;
    }
    if (tree[curSuff].nx[x]) {
        suff = tree[curSuff].nx[x];
        tree[suff].cnt++;
        return;
    }
    suff = ++num;
    tree[num].len = tree[curSuff].len+2;
    tree[num].cnt = 1;
    tree[curSuff].nx[x] = num;
    if (tree[num].len == 1) {
        tree[num].link = 2;
        tree[2].adj.push_back(num);
        return;
    }
    while (1) {
        curSuff = tree[curSuff].link;
        curLen = tree[curSuff].len;
        if (p-1-curLen >= 0 && s[p-1-curLen] == s[p]) {
            tree[num].link = tree[curSuff].nx[x];
            tree[tree[curSuff].nx[x]].adj.push_back(num);
            break;
        }
    }
}

void dfs(int cur) {
    for (int nx : tree[cur].adj) {
        dfs(nx);
        tree[cur].cnt += tree[nx].cnt;
    }
    ans = max(ans,tree[cur].len*tree[cur].cnt);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> s;
    num = suff = 2;
    tree[1].len = -1, tree[1].link = 1;
    tree[2].len = 0, tree[2].link = 1;
    tree[1].adj.push_back(2);
    for (int i = 0; i < s.length(); i++) insert(i);
    dfs(1);
    cout << ans << '\n';
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < s.length(); i++) insert(i);
      |                     ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 44876 KB Output is correct
2 Correct 22 ms 44936 KB Output is correct
3 Correct 22 ms 44916 KB Output is correct
4 Correct 23 ms 44860 KB Output is correct
5 Correct 23 ms 44868 KB Output is correct
6 Correct 23 ms 44872 KB Output is correct
7 Correct 25 ms 44876 KB Output is correct
8 Correct 24 ms 44932 KB Output is correct
9 Correct 22 ms 44876 KB Output is correct
10 Correct 22 ms 44860 KB Output is correct
11 Correct 23 ms 44932 KB Output is correct
12 Correct 23 ms 44832 KB Output is correct
13 Correct 23 ms 44876 KB Output is correct
14 Correct 23 ms 44876 KB Output is correct
15 Correct 22 ms 44896 KB Output is correct
16 Correct 22 ms 44876 KB Output is correct
17 Correct 22 ms 44932 KB Output is correct
18 Correct 23 ms 44888 KB Output is correct
19 Correct 25 ms 44940 KB Output is correct
20 Correct 23 ms 44876 KB Output is correct
21 Correct 23 ms 44876 KB Output is correct
22 Correct 23 ms 44904 KB Output is correct
23 Correct 24 ms 44880 KB Output is correct
24 Correct 24 ms 44860 KB Output is correct
25 Correct 22 ms 44884 KB Output is correct
26 Correct 22 ms 44876 KB Output is correct
27 Correct 22 ms 44936 KB Output is correct
28 Correct 22 ms 44820 KB Output is correct
29 Correct 22 ms 44928 KB Output is correct
30 Correct 23 ms 44932 KB Output is correct
31 Correct 21 ms 44876 KB Output is correct
32 Correct 23 ms 44928 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 44876 KB Output is correct
2 Correct 23 ms 44936 KB Output is correct
3 Correct 25 ms 44940 KB Output is correct
4 Correct 25 ms 44960 KB Output is correct
5 Correct 24 ms 45004 KB Output is correct
6 Correct 23 ms 44924 KB Output is correct
7 Correct 23 ms 44932 KB Output is correct
8 Correct 22 ms 44932 KB Output is correct
9 Correct 24 ms 44920 KB Output is correct
10 Correct 23 ms 44856 KB Output is correct
11 Correct 22 ms 44880 KB Output is correct
12 Correct 23 ms 44876 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 45516 KB Output is correct
2 Correct 24 ms 45496 KB Output is correct
3 Correct 24 ms 45840 KB Output is correct
4 Correct 25 ms 45744 KB Output is correct
5 Correct 24 ms 44984 KB Output is correct
6 Correct 23 ms 45132 KB Output is correct
7 Correct 23 ms 45312 KB Output is correct
8 Correct 23 ms 44876 KB Output is correct
9 Correct 23 ms 44976 KB Output is correct
10 Correct 23 ms 45004 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 51348 KB Output is correct
2 Correct 37 ms 49996 KB Output is correct
3 Correct 38 ms 54476 KB Output is correct
4 Correct 37 ms 52236 KB Output is correct
5 Correct 39 ms 46200 KB Output is correct
6 Correct 33 ms 47144 KB Output is correct
7 Correct 34 ms 48460 KB Output is correct
8 Correct 25 ms 45200 KB Output is correct
9 Correct 28 ms 47288 KB Output is correct
10 Correct 40 ms 46020 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 64180 KB Output is correct
2 Correct 63 ms 57456 KB Output is correct
3 Correct 68 ms 73588 KB Output is correct
4 Correct 63 ms 61668 KB Output is correct
5 Correct 82 ms 49936 KB Output is correct
6 Correct 60 ms 56728 KB Output is correct
7 Correct 58 ms 54476 KB Output is correct
8 Correct 30 ms 45856 KB Output is correct
9 Correct 30 ms 45780 KB Output is correct
10 Correct 71 ms 48980 KB Output is correct
11 Correct 66 ms 58000 KB Output is correct
12 Correct 33 ms 48016 KB Output is correct