oj.uz

Submission #31398

# Submission time Handle Problem Language Result Execution time Memory
31398 2017-08-21T05:46:06 Z nickyrio Palindromes (APIO14_palindrome) C++14
100 / 100
 76 ms 70532 KB 
#include <bits/stdc++.h>


using namespace std;
#define N 350000

struct Node {
    int cnt, len, sufflink, next[26];
}tree[N];

vector<int> e[N];

struct PalindromicTree {
    string s;
    int currNode, ptr;
    long long ans;
    PalindromicTree(string s): s(s) {
        currNode = ptr = 1;
        for(int i = 0; i<N; i++) {
            tree[i].len = tree[i].cnt = tree[i].sufflink = 0;
            for (int j = 0; j<26; j++) tree[i].next[j] = 0;
        }
        tree[0].len = -1; tree[0].sufflink = 0;
        for (int i = 0; i<(int) s.size(); i++) insert(i);
    }
    long long getMaxAns() {
        ans = 0;
        dfs(1);
        return ans;
    }
private:
    void insert(int pos) {
        int cur = currNode;
        int let = s[pos] - 'a';
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && s[pos] == s[pos - curLen - 1]) break;
            cur = tree[cur].sufflink;
        }

        if (tree[cur].next[let]) {
            currNode = tree[cur].next[let];
            tree[currNode].cnt++;
            return;
        }

        currNode = ++ptr;
        tree[cur].next[let] = ptr;
        tree[ptr].cnt = 1;
        tree[ptr].len = tree[cur].len + 2;

        if (tree[ptr].len == 1) {
            tree[ptr].sufflink = 1;
            e[1].push_back(ptr);
            return;
        }

        cur = tree[cur].sufflink;
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && s[pos] == s[pos - curLen - 1]) {
                tree[currNode].sufflink = tree[cur].next[let];
                e[tree[currNode].sufflink].push_back(ptr);
                return;
            }
            cur = tree[cur].sufflink;
        }
    }

    void dfs(int u) {
        for (int v : e[u]) {
            dfs(v);
            tree[u].cnt += tree[v].cnt;
        }
        ans = max(ans, 1ll * tree[u].len * 1ll * tree[u].cnt);
    }

};
string s;
int main() {
    //freopen("palindrome.inp","r",stdin);
    //freopen("palindrome.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(NULL);
    cin.tie(NULL);cout.tie(NULL);
    cin>>s;
    PalindromicTree PT(s);
    cout<<PT.getMaxAns();
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 50340 KB Output is correct
2 Correct 16 ms 50292 KB Output is correct
3 Correct 19 ms 50512 KB Output is correct
4 Correct 9 ms 50456 KB Output is correct
5 Correct 13 ms 50160 KB Output is correct
6 Correct 19 ms 50160 KB Output is correct
7 Correct 9 ms 50292 KB Output is correct
8 Correct 6 ms 50028 KB Output is correct
9 Correct 16 ms 50028 KB Output is correct
10 Correct 16 ms 50028 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55056 KB Output is correct
2 Correct 26 ms 54288 KB Output is correct
3 Correct 29 ms 56784 KB Output is correct
4 Correct 29 ms 55528 KB Output is correct
5 Correct 26 ms 51460 KB Output is correct
6 Correct 9 ms 51900 KB Output is correct
7 Correct 26 ms 53020 KB Output is correct
8 Correct 13 ms 50404 KB Output is correct
9 Correct 6 ms 51716 KB Output is correct
10 Correct 29 ms 51196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 65324 KB Output is correct
2 Correct 33 ms 61584 KB Output is correct
3 Correct 43 ms 70532 KB Output is correct
4 Correct 53 ms 63896 KB Output is correct
5 Correct 76 ms 55520 KB Output is correct
6 Correct 63 ms 60024 KB Output is correct
7 Correct 56 ms 58816 KB Output is correct
8 Correct 33 ms 51164 KB Output is correct
9 Correct 29 ms 51164 KB Output is correct
10 Correct 46 ms 54596 KB Output is correct
11 Correct 49 ms 61848 KB Output is correct
12 Correct 33 ms 52480 KB Output is correct