oj.uz

Submission #308047

# Submission time Handle Problem Language Result Execution time Memory
308047 2020-09-30T00:48:41 Z Elephant52 Palindromes (APIO14_palindrome) C++11
100 / 100
 83 ms 66428 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vpi;

#define INF 1000000000
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)

void setIO(string name) {
    freopen((name+".in").c_str(), "r", stdin); 
    freopen((name+".out").c_str(), "w", stdout);
}

string s;

struct node {
    int next[26], suflink, len;
    ll num;
    node() {};
    vi adj;
} tree[300001];

//node tree[300001];
int num, suf;

bool add_letter(int pos) { //return 1 on new palindromes
    int cur = suf, letter = (s[pos]-'a'), curlen = 0;
    
    while(1) { //find longest palindromic suffix of s[0...pos-1] that can include s[pos]
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) break;
        cur = tree[cur].suflink;
    }
    
    if (tree[cur].next[letter]) { //if there exists a link from smaller palindrome to s[pos] + pal + s[pos] then do nothing
        suf = tree[cur].next[letter];
        tree[suf].num++;
        return 0;
    }
    
    //create a new palindrome with id num+1 in the tree
    
    suf = ++num;
    tree[num].num = 1;
    tree[num].len = tree[cur].len + 2; //add on s[pos]
    tree[cur].next[letter] = num;
    
    if (tree[num].len == 1) {
        tree[num].suflink = 2; //link to the empty palindrome
        tree[2].adj.PB(num);
        return 1;
    } 
    
    while(1) {
        cur = tree[cur].suflink;
        curlen = tree[cur].len;
        if (pos > curlen && s[pos-1-curlen] == s[pos]) {
            tree[num].suflink = tree[cur].next[letter];
            tree[tree[cur].next[letter]].adj.PB(num);
            break;
        }
    }
    
    return 1;
}

void dfs(int cur = 1) {
    for (auto edge : tree[cur].adj) {
        dfs(edge);
        tree[cur].num += tree[edge].num;
    }
}

void init() {
    num = suf = 2;
    tree[1].len = -1, tree[2].len = 0;
    tree[1].suflink = tree[2].suflink = 1;
    tree[1].adj.PB(2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> s;
    
    init();
    
    rep(i,0,s.length()) add_letter(i);
    
    ll ans = 0;
    
    dfs();
    
    rep(i,1,300001) ans = max(ans, (long long)tree[i].len * tree[i].num);
    
    cout << ans << endl;

    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:15:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 | #define rep(i,a,b) for (int i = a; i < b; i++)
......
   96 |     rep(i,0,s.length()) add_letter(i);
      |         ~~~~~~~~~~~~~~                
palindrome.cpp:96:5: note: in expansion of macro 'rep'
   96 |     rep(i,0,s.length()) add_letter(i);
      |     ^~~
palindrome.cpp: In function 'void setIO(std::string)':
palindrome.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   18 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindrome.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 42672 KB Output is correct
2 Correct 25 ms 42624 KB Output is correct
3 Correct 25 ms 42668 KB Output is correct
4 Correct 25 ms 42624 KB Output is correct
5 Correct 25 ms 42624 KB Output is correct
6 Correct 25 ms 42624 KB Output is correct
7 Correct 25 ms 42624 KB Output is correct
8 Correct 26 ms 42624 KB Output is correct
9 Correct 26 ms 42616 KB Output is correct
10 Correct 25 ms 42624 KB Output is correct
11 Correct 26 ms 42624 KB Output is correct
12 Correct 25 ms 42616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 43136 KB Output is correct
2 Correct 27 ms 43136 KB Output is correct
3 Correct 26 ms 43392 KB Output is correct
4 Correct 27 ms 43264 KB Output is correct
5 Correct 26 ms 42752 KB Output is correct
6 Correct 27 ms 42880 KB Output is correct
7 Correct 26 ms 43008 KB Output is correct
8 Correct 26 ms 42624 KB Output is correct
9 Correct 25 ms 42624 KB Output is correct
10 Correct 26 ms 42616 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 48120 KB Output is correct
2 Correct 39 ms 47096 KB Output is correct
3 Correct 38 ms 50684 KB Output is correct
4 Correct 39 ms 48760 KB Output is correct
5 Correct 41 ms 43904 KB Output is correct
6 Correct 34 ms 44664 KB Output is correct
7 Correct 36 ms 45696 KB Output is correct
8 Correct 27 ms 43008 KB Output is correct
9 Correct 29 ms 44416 KB Output is correct
10 Correct 37 ms 43648 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 59392 KB Output is correct
2 Correct 59 ms 54268 KB Output is correct
3 Correct 63 ms 66428 KB Output is correct
4 Correct 61 ms 57472 KB Output is correct
5 Correct 83 ms 47512 KB Output is correct
6 Correct 60 ms 52992 KB Output is correct
7 Correct 56 ms 51456 KB Output is correct
8 Correct 31 ms 43272 KB Output is correct
9 Correct 31 ms 43272 KB Output is correct
10 Correct 66 ms 46536 KB Output is correct
11 Correct 62 ms 54656 KB Output is correct
12 Correct 33 ms 45056 KB Output is correct