oj.uz

Submission #885042

# Submission time Handle Problem Language Result Execution time Memory
885042 2023-12-08T20:45:56 Z patrikpavic2 Palindromes (APIO14_palindrome) C++17
100 / 100
 260 ms 81360 KB 
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
 
#define PB push_back
 
using namespace std;
 
typedef long long ll;
 
const int N = 3e5 + 500;
const int INF = 0x3f3f3f3f;
const int ALP = 26;
 
struct node{
    node *ch[ALP], *bk;
    int len, cnt;
    node() { len = 0, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch)); }
    node(int _len) { len = _len, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch));  }
};
 
node *n0, *n1;
vector < node* > v;
 
node* create_eertree(string &s){
    n0 = new node(0);
    n1 = new node(-1); 
    n0->bk = n1; n1->bk = n1;
    node* cur = n0;
    for(int i = 0;i < (int)s.size();i++){
        for(;cur->len+1>i||s[i-cur->len-1]!=s[i];cur=cur->bk);
        node *rmb = cur->bk;
        if(!cur->ch[s[i]-'a'])
            cur->ch[s[i]-'a'] = new node(cur->len + 2);
        cur = cur->ch[s[i] - 'a']; cur->cnt++;
        for(;rmb->len+1>i||s[i-rmb->len-1]!=s[i];rmb=rmb->bk);
        if(cur->len == 1)
            cur->bk = n0;
        else{
            if(!rmb->ch[s[i] - 'a']) 
            	rmb->ch[s[i] - 'a'] = new node(rmb->len + 2);
            cur->bk = rmb->ch[s[i] - 'a'];
        }
    }
    return n0;
}
 
 
bool cmp(node* X, node* Y){
    return X->len > Y->len;
}
 
 
string s;
 
void dfs(node* x) {
	if(!x) return;
	v.PB(x);
	for(int i = 0;i < 26;i++)
		if(x->ch[i]) dfs(x->ch[i]);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    ll mx = 0;
    node* root = create_eertree(s);
    dfs(root); dfs(root->bk);
    sort(v.begin(), v.end(), cmp);
    for(int i = 0;i < (int)v.size();i++){
        mx = max(mx, (ll)v[i]->len * v[i]->cnt);
        v[i]->bk->cnt += v[i]->cnt;
    }
    cout << mx << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 3 ms 3160 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2908 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 2140 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 26580 KB Output is correct
2 Correct 31 ms 25700 KB Output is correct
3 Correct 45 ms 26580 KB Output is correct
4 Correct 41 ms 26068 KB Output is correct
5 Correct 31 ms 26064 KB Output is correct
6 Correct 32 ms 19160 KB Output is correct
7 Correct 24 ms 21724 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 8 ms 6748 KB Output is correct
10 Correct 24 ms 22492 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 80684 KB Output is correct
2 Correct 123 ms 78284 KB Output is correct
3 Correct 218 ms 81356 KB Output is correct
4 Correct 127 ms 78756 KB Output is correct
5 Correct 112 ms 80040 KB Output is correct
6 Correct 98 ms 68816 KB Output is correct
7 Correct 100 ms 62412 KB Output is correct
8 Correct 5 ms 992 KB Output is correct
9 Correct 4 ms 992 KB Output is correct
10 Correct 98 ms 64464 KB Output is correct
11 Correct 260 ms 81360 KB Output is correct
12 Correct 11 ms 8164 KB Output is correct