oj.uz

Submission #551787

# Submission time Handle Problem Language Result Execution time Memory
551787 2022-04-21T14:23:13 Z MarcoMeijer Palindromes (APIO14_palindrome) C++14
100 / 100
 25 ms 35328 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
//===================//
//  Added libraries  //
//===================//
 
//===================//
//end added libraries//
//===================//
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 3e5+4;
 
int n;
 
struct Node {
    int nxt[26], sufflink, len;
    int cnt=1;
} tree[MX];
 
string s;
int suf, num;
 
void initTree() {
    num = suf = 2;
    tree[1].len = -1; tree[1].sufflink = 1;
    tree[2].len =  0; tree[2].sufflink = 1;
}
void addLetter(int pos) {
    int cur = suf, curLen = 0;
 
    while(1) {
        curLen = tree[cur].len;
        if(pos-1-curLen >= 0 && s[pos-1-curLen] == s[pos])
            break;
        cur = tree[cur].sufflink;
    }
    if(tree[cur].nxt[s[pos]]) {
        suf = tree[cur].nxt[s[pos]];
        tree[suf].cnt++;
        return;
    }
 
    suf = ++num;
    tree[num].len = tree[cur].len+2;
    tree[cur].nxt[s[pos]] = suf;
 
    if(tree[num].len == 1) {
        tree[num].sufflink = 2;
        return;
    }
 
    while(1) {
        cur = tree[cur].sufflink;
        curLen = tree[cur].len;
        if(pos-1-curLen >= 0 && s[pos-1-curLen] == s[pos]) {
            tree[num].sufflink = tree[cur].nxt[s[pos]];
            break;
        }
    }
}
 
void program() {
    IN(s); n=s.sz;
    FOR(i,s) i-='a';
    initTree();
    RE(i,n) addLetter(i);
    ll ans=0;
    REV(u,1,num+1) {
        tree[tree[u].sufflink].cnt += tree[u].cnt;
        ans = max(ans, (ll)tree[u].cnt*(ll)tree[u].len);
    }
    OUTL(ans);
}

Compilation message

palindrome.cpp: In function 'void addLetter(int)':
palindrome.cpp:93:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   93 |     if(tree[cur].nxt[s[pos]]) {
      |                            ^
palindrome.cpp:94:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   94 |         suf = tree[cur].nxt[s[pos]];
      |                                   ^
palindrome.cpp:101:25: warning: array subscript has type 'char' [-Wchar-subscripts]
  101 |     tree[cur].nxt[s[pos]] = suf;
      |                         ^
palindrome.cpp:112:54: warning: array subscript has type 'char' [-Wchar-subscripts]
  112 |             tree[num].sufflink = tree[cur].nxt[s[pos]];
      |                                                      ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 34360 KB Output is correct
2 Correct 14 ms 34336 KB Output is correct
3 Correct 15 ms 34352 KB Output is correct
4 Correct 14 ms 34376 KB Output is correct
5 Correct 17 ms 34260 KB Output is correct
6 Correct 17 ms 34260 KB Output is correct
7 Correct 15 ms 34368 KB Output is correct
8 Correct 15 ms 34312 KB Output is correct
9 Correct 14 ms 34260 KB Output is correct
10 Correct 14 ms 34372 KB Output is correct
11 Correct 14 ms 34312 KB Output is correct
12 Correct 16 ms 34268 KB Output is correct
13 Correct 13 ms 34372 KB Output is correct
14 Correct 13 ms 34348 KB Output is correct
15 Correct 13 ms 34260 KB Output is correct
16 Correct 13 ms 34260 KB Output is correct
17 Correct 14 ms 34260 KB Output is correct
18 Correct 13 ms 34260 KB Output is correct
19 Correct 14 ms 34336 KB Output is correct
20 Correct 17 ms 34384 KB Output is correct
21 Correct 18 ms 34312 KB Output is correct
22 Correct 15 ms 34272 KB Output is correct
23 Correct 15 ms 34320 KB Output is correct
24 Correct 14 ms 34260 KB Output is correct
25 Correct 13 ms 34260 KB Output is correct
26 Correct 14 ms 34260 KB Output is correct
27 Correct 15 ms 34380 KB Output is correct
28 Correct 14 ms 34376 KB Output is correct
29 Correct 14 ms 34388 KB Output is correct
30 Correct 15 ms 34316 KB Output is correct
31 Correct 14 ms 34372 KB Output is correct
32 Correct 17 ms 34256 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34260 KB Output is correct
2 Correct 14 ms 34260 KB Output is correct
3 Correct 14 ms 34404 KB Output is correct
4 Correct 16 ms 34440 KB Output is correct
5 Correct 16 ms 34356 KB Output is correct
6 Correct 15 ms 34260 KB Output is correct
7 Correct 17 ms 34276 KB Output is correct
8 Correct 17 ms 34284 KB Output is correct
9 Correct 17 ms 34288 KB Output is correct
10 Correct 13 ms 34260 KB Output is correct
11 Correct 15 ms 34292 KB Output is correct
12 Correct 16 ms 34340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 34388 KB Output is correct
2 Correct 14 ms 34388 KB Output is correct
3 Correct 16 ms 34380 KB Output is correct
4 Correct 15 ms 34388 KB Output is correct
5 Correct 18 ms 34380 KB Output is correct
6 Correct 17 ms 34356 KB Output is correct
7 Correct 15 ms 34376 KB Output is correct
8 Correct 17 ms 34388 KB Output is correct
9 Correct 17 ms 34388 KB Output is correct
10 Correct 16 ms 34388 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34624 KB Output is correct
2 Correct 17 ms 34696 KB Output is correct
3 Correct 17 ms 34584 KB Output is correct
4 Correct 17 ms 34644 KB Output is correct
5 Correct 16 ms 34644 KB Output is correct
6 Correct 15 ms 34644 KB Output is correct
7 Correct 16 ms 34640 KB Output is correct
8 Correct 15 ms 34644 KB Output is correct
9 Correct 15 ms 34640 KB Output is correct
10 Correct 16 ms 34680 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35292 KB Output is correct
2 Correct 24 ms 35292 KB Output is correct
3 Correct 21 ms 35292 KB Output is correct
4 Correct 23 ms 35284 KB Output is correct
5 Correct 25 ms 35292 KB Output is correct
6 Correct 22 ms 35292 KB Output is correct
7 Correct 22 ms 35292 KB Output is correct
8 Correct 23 ms 35328 KB Output is correct
9 Correct 20 ms 35252 KB Output is correct
10 Correct 24 ms 35280 KB Output is correct
11 Correct 22 ms 35292 KB Output is correct
12 Correct 23 ms 35252 KB Output is correct