oj.uz

Submission #34030

# Submission time Handle Problem Language Result Execution time Memory
34030 2017-11-06T11:31:59 Z nickyrio Palindromes (APIO14_palindrome) C++14
73 / 100
 23 ms 21848 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 100100
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
template<typename T> inline void read(T &x) {
    char c;
    while (!isdigit(c = getchar()));
    x = 0;
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
}
template<typename T> inline void write(T x) {
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

struct Node {
    int next[26];
    int suff, len, cnt;
};

struct PalindromicTree {
    vector<Node> tree;
    int n, currNode, ptr;
    string st;
    vector<vector<int> > e;
    void reset(string st) {
        n = st.size();
        this -> st = st;
        tree.resize(n + 3);
        e.resize(n + 3);
        currNode = 0;
        tree[0].len = -1;tree[0].suff = 0;
        tree[1].len = 0;tree[1].suff = 0;
        ptr = currNode = 1;
        REP(i, n) add(i);
    }

    long long getAns() {
        dfs(1);
        long long ans = 0;
        FOR(i, 2, ptr) {
            ans = max(ans, 1ll * tree[i].cnt * tree[i].len);
        }
        return ans;
    }
    void add(int pos) {
        int idx = st[pos] - 'a';
        int cur = currNode;
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) break;
            cur = tree[cur].suff;
        }
        if (tree[cur].next[idx]) {
            currNode = tree[cur].next[idx];
            tree[currNode].cnt++;
            return;
        }

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

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

        cur = tree[cur].suff;
        while (true) {
            int curLen = tree[cur].len;
            if (pos - curLen >= 1 && st[pos] == st[pos - curLen - 1]) {
                tree[currNode].suff = tree[cur].next[idx];
                e[tree[cur].next[idx]].push_back(ptr);
                return;
            }
            cur = tree[cur].suff;
        }
    }
    void dfs(int u) {
        for (int v : e[u]) {
            dfs(v);
            tree[u].cnt += tree[v].cnt;
        }
    }
}PT;

char s[N];
string st;

int main() {
    IO;
    scanf("%s", s);
    string st = s;
    PT.reset(st);
    write(PT.getAns());
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:110:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
                   ^

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3896 KB Output is correct
2 Correct 0 ms 3884 KB Output is correct
3 Correct 0 ms 4036 KB Output is correct
4 Correct 0 ms 3996 KB Output is correct
5 Correct 0 ms 3620 KB Output is correct
6 Correct 0 ms 3752 KB Output is correct
7 Correct 0 ms 3884 KB Output is correct
8 Correct 0 ms 3488 KB Output is correct
9 Correct 0 ms 3488 KB Output is correct
10 Correct 0 ms 3620 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20464 KB Output is correct
2 Correct 23 ms 19848 KB Output is correct
3 Correct 13 ms 21848 KB Output is correct
4 Correct 13 ms 20840 KB Output is correct
5 Correct 16 ms 17216 KB Output is correct
6 Correct 13 ms 17700 KB Output is correct
7 Correct 19 ms 18652 KB Output is correct
8 Correct 6 ms 16160 KB Output is correct
9 Correct 3 ms 17316 KB Output is correct
10 Correct 16 ms 17084 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -