oj.uz

Submission #547699

# Submission time Handle Problem Language Result Execution time Memory
547699 2022-04-11T13:15:35 Z MilosMilutinovic Palindromes (APIO14_palindrome) C++14
100 / 100
 53 ms 63268 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 300000;

/* template by MladenP */
struct PalTree {
    #define P_SIGMA 26
    #define FIRST_NODE 1
    #define SECOND_NODE 2
    struct Node {
        int len, cnt, dub, slink;
        int to[P_SIGMA];
        Node() { len = cnt = dub = slink = 0; for(int i = 0; i < P_SIGMA; i++) to[i] = 0; }
        Node(int _len, int _cnt, int _dub, int _slink) {
            len = _len; cnt = _cnt; dub = _dub; slink = _slink;
            for(int i = 0; i < P_SIGMA; i++) to[i] = 0;
        }
    };
    string s;
    vector<Node> pt;
    int suff;
    int toidx(char c) { return c-'a'; }
    void addLetter(char c) {
        s += c; int len = s.size();
        while(c != s[len-2-pt[suff].len]) {
            suff = pt[suff].slink;
        }
        int nd = pt[suff].to[toidx(c)];
        if(nd == 0) {
            nd = pt.size();
            pt[suff].to[toidx(c)] = nd;
            pt.push_back(Node(pt[suff].len+2, 0, 0, 0));
            if(suff == FIRST_NODE) {
                pt[nd].slink = SECOND_NODE;
            } else {
                int u = pt[suff].slink;
                while(c != s[len-2-pt[u].len]) {
                    u = pt[u].slink;
                }
                pt[nd].slink = pt[u].to[toidx(c)];
            }
            pt[nd].dub = pt[pt[nd].slink].dub+1;
        }
        pt[nd].cnt++;
        suff = nd;
    }
    void init() {
        pt.clear();
        s = "";
        suff = 2;
        pt.push_back(Node(0, 0, 0, 0));
        pt.push_back(Node(-1, 0, 0, FIRST_NODE)); ///first node
        pt.push_back(Node(0, 0, 0, FIRST_NODE)); ///second node
    }
    Node &operator[](int idx) {
        if(idx >= pt.size()) {
            cerr << "Index out of bounds" <<endl;
            return pt[0];
        }
        return pt[idx];
    }
};

PalTree pp;

int main() {
	char ss[N];
	int n, i;

	scanf("%s", ss);
	pp.init(), n = strlen(ss);
	for (i = 0; i < n; i++)
		pp.addLetter(ss[i]);
	long long ans = 0;
	for (i = pp.pt.size() - 1; i > 2; i--) {
		ans = max(ans, (long long) pp[i].len * pp[i].cnt);
		pp[pp[i].slink].cnt += pp[i].cnt;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

palindrome.cpp: In member function 'PalTree::Node& PalTree::operator[](int)':
palindrome.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PalTree::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(idx >= pt.size()) {
      |            ~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%s", ss);
      |  ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2576 KB Output is correct
2 Correct 2 ms 2576 KB Output is correct
3 Correct 2 ms 2576 KB Output is correct
4 Correct 2 ms 2576 KB Output is correct
5 Correct 2 ms 2576 KB Output is correct
6 Correct 2 ms 2576 KB Output is correct
7 Correct 2 ms 2576 KB Output is correct
8 Correct 1 ms 708 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 1652 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16348 KB Output is correct
2 Correct 15 ms 16200 KB Output is correct
3 Correct 15 ms 16288 KB Output is correct
4 Correct 16 ms 16284 KB Output is correct
5 Correct 15 ms 16288 KB Output is correct
6 Correct 16 ms 16204 KB Output is correct
7 Correct 16 ms 16288 KB Output is correct
8 Correct 4 ms 988 KB Output is correct
9 Correct 7 ms 4920 KB Output is correct
10 Correct 14 ms 16196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 63156 KB Output is correct
2 Correct 52 ms 63132 KB Output is correct
3 Correct 51 ms 63076 KB Output is correct
4 Correct 53 ms 63184 KB Output is correct
5 Correct 53 ms 63268 KB Output is correct
6 Correct 49 ms 63144 KB Output is correct
7 Correct 37 ms 31960 KB Output is correct
8 Correct 9 ms 1600 KB Output is correct
9 Correct 9 ms 1588 KB Output is correct
10 Correct 34 ms 32024 KB Output is correct
11 Correct 52 ms 63216 KB Output is correct
12 Correct 12 ms 5088 KB Output is correct