oj.uz

Submission #48303

# Submission time Handle Problem Language Result Execution time Memory
48303 2018-05-11T15:02:56 Z nickyrio Palindromes (APIO14_palindrome) C++17
100 / 100
 104 ms 71568 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 (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 (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 43 ms 48248 KB Output is correct
2 Correct 45 ms 48360 KB Output is correct
3 Correct 42 ms 48440 KB Output is correct
4 Correct 43 ms 48608 KB Output is correct
5 Correct 43 ms 48608 KB Output is correct
6 Correct 42 ms 48608 KB Output is correct
7 Correct 42 ms 48704 KB Output is correct
8 Correct 43 ms 48704 KB Output is correct
9 Correct 43 ms 48704 KB Output is correct
10 Correct 42 ms 48808 KB Output is correct
11 Correct 42 ms 48808 KB Output is correct
12 Correct 44 ms 48808 KB Output is correct
13 Correct 43 ms 48808 KB Output is correct
14 Correct 45 ms 48808 KB Output is correct
15 Correct 47 ms 48808 KB Output is correct
16 Correct 42 ms 48848 KB Output is correct
17 Correct 43 ms 48848 KB Output is correct
18 Correct 42 ms 48912 KB Output is correct
19 Correct 43 ms 48916 KB Output is correct
20 Correct 42 ms 48916 KB Output is correct
21 Correct 45 ms 48928 KB Output is correct
22 Correct 42 ms 48928 KB Output is correct
23 Correct 43 ms 48928 KB Output is correct
24 Correct 45 ms 48940 KB Output is correct
25 Correct 47 ms 48940 KB Output is correct
26 Correct 43 ms 48940 KB Output is correct
27 Correct 44 ms 48940 KB Output is correct
28 Correct 44 ms 48940 KB Output is correct
29 Correct 45 ms 48940 KB Output is correct
30 Correct 53 ms 48940 KB Output is correct
31 Correct 50 ms 48968 KB Output is correct
32 Correct 46 ms 48968 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 48968 KB Output is correct
2 Correct 44 ms 49040 KB Output is correct
3 Correct 43 ms 49112 KB Output is correct
4 Correct 43 ms 49112 KB Output is correct
5 Correct 46 ms 49120 KB Output is correct
6 Correct 45 ms 49124 KB Output is correct
7 Correct 44 ms 49124 KB Output is correct
8 Correct 43 ms 49124 KB Output is correct
9 Correct 43 ms 49124 KB Output is correct
10 Correct 43 ms 49124 KB Output is correct
11 Correct 44 ms 49124 KB Output is correct
12 Correct 44 ms 49148 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49536 KB Output is correct
2 Correct 43 ms 49584 KB Output is correct
3 Correct 47 ms 49824 KB Output is correct
4 Correct 44 ms 49824 KB Output is correct
5 Correct 44 ms 49824 KB Output is correct
6 Correct 50 ms 49824 KB Output is correct
7 Correct 45 ms 49824 KB Output is correct
8 Correct 45 ms 49824 KB Output is correct
9 Correct 44 ms 49824 KB Output is correct
10 Correct 44 ms 49824 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 54444 KB Output is correct
2 Correct 54 ms 54444 KB Output is correct
3 Correct 57 ms 56452 KB Output is correct
4 Correct 57 ms 56452 KB Output is correct
5 Correct 56 ms 56452 KB Output is correct
6 Correct 52 ms 56452 KB Output is correct
7 Correct 52 ms 56452 KB Output is correct
8 Correct 52 ms 56452 KB Output is correct
9 Correct 55 ms 56452 KB Output is correct
10 Correct 52 ms 56452 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 65668 KB Output is correct
2 Correct 90 ms 65668 KB Output is correct
3 Correct 90 ms 71568 KB Output is correct
4 Correct 83 ms 71568 KB Output is correct
5 Correct 99 ms 71568 KB Output is correct
6 Correct 81 ms 71568 KB Output is correct
7 Correct 75 ms 71568 KB Output is correct
8 Correct 49 ms 71568 KB Output is correct
9 Correct 55 ms 71568 KB Output is correct
10 Correct 98 ms 71568 KB Output is correct
11 Correct 104 ms 71568 KB Output is correct
12 Correct 52 ms 71568 KB Output is correct