oj.uz

답안 #84503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84503 2018-11-15T18:10:55 Z popovicirobert 회문 (APIO14_palindrome) C++14
23 / 100
 394 ms 51372 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;
const int B = 57;

char str[MAXN + 1];

ull pw[MAXN + 1], hsh[MAXN + 1];

inline ull get_hsh(int l, int r) {
    return hsh[r] - hsh[l - 1] * pw[r - l + 1];
}

int len[2 * MAXN + 5];

inline void manacher(int n) {
    vector <char> aux(2 * n + 5);
    int i, sz = 0;
    for(i = 1; i <= n; i++) {
        aux[++sz] = '*';
        aux[++sz] = str[i];
    }
    aux[++sz] = '*';
    int p = 0;
    for(i = 1; i <= sz; i++) {
        if(p + len[p] >= i) {
            len[i] = min(len[2 * p - i], p + len[p] - i);
        }
        while(i - len[i] > 0 && i + len[i] <= sz && aux[i - len[i]] == aux[i + len[i]]) {
            len[i]++;
        }
        if(i + len[i] > p + len[p]) {
            p = i;
        }
    }
}

unordered_map <ull, int> mp;

struct Trie {
    vector <int> sons;
    ll lvl, sz;
};

vector <Trie> v;
ll ans = 0;
int cnt = 0;

void dfs(int nod, int lvl) {
    for(auto it : v[nod].sons) {
        dfs(it, lvl + 1);
        v[nod].sz += v[it].sz;
    }
    if(2 * lvl < v[nod].lvl) {
        while(1) {

        }
    }
    cnt++;
    ans = max(ans, 1LL * v[nod].lvl * v[nod].sz);
}

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i;
    ios::sync_with_stdio(false);
    //srand(time(NULL));
    cin >> str + 1;
    int n = strlen(str + 1);
    manacher(n);
    pw[0] = 1;
    for(i = 1; i <= n; i++) {
        pw[i] = pw[i - 1] * B;
        hsh[i] = hsh[i - 1] * B + str[i] - 'a' + 1;
    }
    int id = 1;
    v.resize(2);
    for(i = 2; i <= 2 * n; i++) {
        int last = 0, j = 0;
        bool ok = 0;
        for(j = len[i] / 2; j >= 1; j--) {
            ull cur = get_hsh(i / 2 - j + 1, i / 2 + j - (1 - i % 2));
            int l = 2 * j - (1 - i % 2);
            ok = 0;
            if(mp[cur] == 0) {
                ok = 1;
                mp[cur] = ++id;
                Trie aux;
                aux.lvl = l;
                aux.sz = 0;
                v.push_back(aux);
            }
            if(last != 0) {
                v[mp[cur]].sons.push_back(last);
            }
            else {
                v[mp[cur]].sz++;
            }
            last = mp[cur];
            if(!ok) {
                break;
            }
        }
        if(ok == 1) {
            v[1].sons.push_back(last);
        }
    }
    dfs(1, 0);
    if(cnt - 1 != mp.size()) {
        while(1) {

        }
    }
    cout << ans;
    /*for(i = 0; i < 40000; i++) {
        cout << (char) ('a' + rand() % 4);
    }*/
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:76:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> str + 1;
            ~~~~^~~
palindrome.cpp:117:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cnt - 1 != mp.size()) {
        ~~~~~~~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 2 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct
13 Correct 2 ms 676 KB Output is correct
14 Correct 2 ms 676 KB Output is correct
15 Correct 2 ms 720 KB Output is correct
16 Correct 2 ms 720 KB Output is correct
17 Correct 2 ms 720 KB Output is correct
18 Correct 2 ms 720 KB Output is correct
19 Correct 2 ms 720 KB Output is correct
20 Correct 2 ms 720 KB Output is correct
21 Correct 2 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 2 ms 748 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 748 KB Output is correct
26 Correct 2 ms 748 KB Output is correct
27 Correct 2 ms 748 KB Output is correct
28 Correct 3 ms 748 KB Output is correct
29 Correct 2 ms 748 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 748 KB Output is correct
32 Correct 2 ms 748 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 2 ms 764 KB Output is correct
4 Correct 2 ms 764 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 2 ms 764 KB Output is correct
7 Correct 2 ms 816 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 2 ms 828 KB Output is correct
11 Correct 2 ms 828 KB Output is correct
12 Correct 2 ms 828 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2320 KB Output is correct
2 Correct 9 ms 2320 KB Output is correct
3 Correct 9 ms 2320 KB Output is correct
4 Correct 8 ms 2320 KB Output is correct
5 Correct 8 ms 2320 KB Output is correct
6 Correct 7 ms 2320 KB Output is correct
7 Correct 7 ms 2320 KB Output is correct
8 Correct 4 ms 2320 KB Output is correct
9 Correct 4 ms 2320 KB Output is correct
10 Incorrect 4 ms 2320 KB Output isn't correct

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 17236 KB Output is correct
2 Correct 70 ms 17236 KB Output is correct
3 Correct 79 ms 17260 KB Output is correct
4 Correct 75 ms 17260 KB Output is correct
5 Correct 66 ms 17260 KB Output is correct
6 Correct 51 ms 17260 KB Output is correct
7 Correct 59 ms 17260 KB Output is correct
8 Correct 15 ms 17260 KB Output is correct
9 Correct 26 ms 17260 KB Output is correct
10 Incorrect 32 ms 17260 KB Output isn't correct

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 51324 KB Output is correct
2 Correct 350 ms 51324 KB Output is correct
3 Correct 394 ms 51372 KB Output is correct
4 Correct 336 ms 51372 KB Output is correct
5 Correct 293 ms 51372 KB Output is correct
6 Correct 263 ms 51372 KB Output is correct
7 Correct 252 ms 51372 KB Output is correct
8 Correct 46 ms 51372 KB Output is correct
9 Correct 43 ms 51372 KB Output is correct
10 Incorrect 136 ms 51372 KB Output isn't correct
11 Halted 0 ms 0 KB -