oj.uz

Submission #31273

# Submission time Handle Problem Language Result Execution time Memory
31273 2017-08-17T16:13:39 Z jokerno1 Palindromes (APIO14_palindrome) C++14
100 / 100
 86 ms 70540 KB 
#include <bits/stdc++.h>
//NickyRio

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 9 ms 50032 KB Output is correct
2 Correct 9 ms 50032 KB Output is correct
3 Correct 19 ms 50032 KB Output is correct
4 Correct 19 ms 50032 KB Output is correct
5 Correct 19 ms 50032 KB Output is correct
6 Correct 6 ms 50032 KB Output is correct
7 Correct 23 ms 50032 KB Output is correct
8 Correct 6 ms 50032 KB Output is correct
9 Correct 13 ms 50032 KB Output is correct
10 Correct 16 ms 50032 KB Output is correct
11 Correct 9 ms 50032 KB Output is correct
12 Correct 23 ms 50032 KB Output is correct
13 Correct 6 ms 50032 KB Output is correct
14 Correct 9 ms 50032 KB Output is correct
15 Correct 16 ms 50032 KB Output is correct
16 Correct 13 ms 50032 KB Output is correct
17 Correct 6 ms 50032 KB Output is correct
18 Correct 13 ms 50032 KB Output is correct
19 Correct 19 ms 50032 KB Output is correct
20 Correct 9 ms 50032 KB Output is correct
21 Correct 19 ms 50032 KB Output is correct
22 Correct 16 ms 50032 KB Output is correct
23 Correct 23 ms 50032 KB Output is correct
24 Correct 16 ms 50032 KB Output is correct
25 Correct 23 ms 50032 KB Output is correct
26 Correct 6 ms 50032 KB Output is correct
27 Correct 13 ms 50032 KB Output is correct
28 Correct 29 ms 50032 KB Output is correct
29 Correct 23 ms 50032 KB Output is correct
30 Correct 6 ms 50032 KB Output is correct
31 Correct 13 ms 50032 KB Output is correct
32 Correct 9 ms 50032 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 50348 KB Output is correct
2 Correct 16 ms 50300 KB Output is correct
3 Correct 16 ms 50516 KB Output is correct
4 Correct 9 ms 50464 KB Output is correct
5 Correct 16 ms 50164 KB Output is correct
6 Correct 19 ms 50164 KB Output is correct
7 Correct 23 ms 50296 KB Output is correct
8 Correct 13 ms 50032 KB Output is correct
9 Correct 9 ms 50032 KB Output is correct
10 Correct 13 ms 50032 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 55060 KB Output is correct
2 Correct 29 ms 54296 KB Output is correct
3 Correct 19 ms 56792 KB Output is correct
4 Correct 16 ms 55532 KB Output is correct
5 Correct 29 ms 51464 KB Output is correct
6 Correct 9 ms 51912 KB Output is correct
7 Correct 36 ms 53024 KB Output is correct
8 Correct 13 ms 50408 KB Output is correct
9 Correct 23 ms 51720 KB Output is correct
10 Correct 29 ms 51200 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 65328 KB Output is correct
2 Correct 59 ms 61588 KB Output is correct
3 Correct 59 ms 70540 KB Output is correct
4 Correct 69 ms 63896 KB Output is correct
5 Correct 56 ms 55524 KB Output is correct
6 Correct 56 ms 60028 KB Output is correct
7 Correct 43 ms 58824 KB Output is correct
8 Correct 23 ms 51168 KB Output is correct
9 Correct 16 ms 51168 KB Output is correct
10 Correct 86 ms 54600 KB Output is correct
11 Correct 79 ms 61852 KB Output is correct
12 Correct 26 ms 52480 KB Output is correct