oj.uz

Submission #77016

# Submission time Handle Problem Language Result Execution time Memory
77016 2018-09-20T04:37:03 Z samuelfgs96 Palindromes (APIO14_palindrome) C++11
73 / 100
 193 ms 132096 KB 
#include <bits/stdc++.h>
 
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 312345;
string s;
int at;
struct No {
    int L, R, p, suff;
    map <char, int> f;
    No() {}
    No(int l, int r, int P) : L(l), R(r), p(P) {}
    inline int len () {
        return R-L+1;
    }
    inline char operator[] (int i) {
        return s[L + i];
    }
    void print() {
        for (int i = 0; i < len(); i++) printf("%c", (*this)[i]);
    }
} t[2*N];
int novo (int L, int R, int p) {
    t[at] = No (L, R, p);
    at++;
    return at-1;
}
void build_suffix_tree () {
    novo (0, -1, -1); //criando raiz
    
    s += "$";
    int i = 0, cn = 0, cd = 0, ns = 0;
    int n = s.size();
    for (int j = 0; j < s.size(); j++) {
        for (; i <= j; i++) {
            if (t[cn].len() == cd ? t[cn].f.count(s[j]) : t[cn][cd] == s[j]) {//CASO 1
                if (t[cn].len() == cd) {
                    cd = 0;
                    cn = t[cn].f[s[j]];
                }
                cd++;
                break;
            } else if (t[cn].len() == cd) {//CASO 2
                t[cn].f[s[j]] = novo(j, n-1, cn);
                if (cn) {
                    cn = t[cn].suff;
                    cd = t[cn].len();
                }
            } else {//CASO 3 (precisa criar o suffix link)
                //quebrar a aresta
                int mid = novo (t[cn].L, t[cn].L + cd - 1, t[cn].p);
                t[t[mid].p].f[t[mid][0]] = mid;
                t[mid].f[s[j]] = novo (j, n-1, mid);
                t[mid].f[t[cn][cd]] = cn;
                t[cn].p = mid;
                t[cn].L += cd;
                if (ns) t[ns].suff = mid;
                //achar o suffix link de mid
                cn = t[mid].p;
                int g;
                if (cn) {
                    cn = t[cn].suff;
                    g = j - cd;
                } else g = i+1;
                while (g < j && g + t[t[cn].f[s[g]]].len() <= j) {
                    cn = t[cn].f[s[g]];
                    g += t[cn].len();
                }
                if (g == j) {
                    t[mid].suff = cn;
                    cd = t[cn].len();
                    ns = 0;
                } else { // g < j
                    ns = mid;
                    cn = t[cn].f[s[g]];
                    cd = j - g;
                }
            }
        }
    }
}
int L[N*2]; //LPS Length Array
void findLongestPalindromicString() {
	string text = s;
	int N = text.size();
    if(N == 0)
        return;
    N = 2*N + 1; //Position count
    L[0] = 0;
    L[1] = 1;
    int C = 1; //centerPosition 
    int R = 2; //centerRightPosition
    int i = 0; //currentRightPosition
    int iMirror; //currentLeftPosition
    int maxLPSLength = 0;
    int maxLPSCenterPosition = 0;
    int start = -1;
    int end = -1;
    int diff = -1;
     
    //Uncomment it to print LPS Length array
    //printf("%d %d ", L[0], L[1]);
    for (i = 2; i < N; i++) 
    {
        //get currentLeftPosition iMirror for currentRightPosition i
        iMirror  = 2*C-i;
        L[i] = 0;
        diff = R - i;
        //If currentRightPosition i is within centerRightPosition R
        if(diff > 0)
            L[i] = min(L[iMirror], diff);
 
        //Attempt to expand palindrome centered at currentRightPosition i
        //Here for odd positions, we compare characters and 
        //if match then increment LPS Length by ONE
        //If even position, we just increment LPS by ONE without 
        //any character comparison
        while ( ((i + L[i]) < N && (i - L[i]) > 0) && 
            ( ((i + L[i] + 1) % 2 == 0) || 
            (text[(i + L[i] + 1)/2] == text[(i - L[i] - 1)/2] )))
        {
            L[i]++;
        }
 
        if(L[i] > maxLPSLength)  // Track maxLPSLength
        {
            maxLPSLength = L[i];
            maxLPSCenterPosition = i;
        }
 
        //If palindrome centered at currentRightPosition i 
        //expand beyond centerRightPosition R,
        //adjust centerPosition C based on expanded palindrome.
        if (i + L[i] > R) 
        {
            C = i;
            R = i + L[i];
        }
        //Uncomment it to print LPS Length array
        //printf("%d ", L[i]);
    }
    //printf("\n");
    start = (maxLPSCenterPosition - maxLPSLength)/2;
    end = start + maxLPSLength - 1;
}
int pos[N], pai[N*2], sz[N*2], ac[N*2], comeco[N];
void dfs (int u, int len) {
	len += t[u].len();
	ac[u] = len;
	if (t[u].R + 1 == (int)s.size()) {
		pos[int(s.size()) - len] = u;
		comeco[u] = int(s.size()) - len;
		sz[u] = 1;
		return ;
	}
	for (auto v : t[u].f) {
		dfs(v.se, len);
		sz[u] += sz[v.se];
		comeco[u] = comeco[v.se];
	}
}
const int LN = 20;
int _log[2*N+10];
struct rmq {
	vector <int> table[20];
	int n;
	rmq () { }
	rmq (int n) : n(n) {
		for (int j = 0; j < 20; j++) table[j].resize(n);
		for (int i = 0; i < n; i++) {
			table[0][i] = L[i];
		}
		for (int j = 1; (1<<j) <= n; j++)
		for (int i = 0; i + (1<<j) <= n; i++)
			table[j][i] = max(table[j-1][i], table[j-1][i+(1<<(j-1))]);
	}
	int query (int l, int r) {
		int sz = r - l + 1;
		int lg = _log[sz];
		return max(table[lg][l], table[lg][r - (1<<lg) + 1]);
	}
} st;

ll ans = 0;
void solve (int u, ll len) {
	for (auto v : t[u].f)
		solve(v.se, len);
}
int main (void) {
	_log[1] = 0;
	for (int i = 2; i < 2*N; i++) {
		_log[i] = _log[i-1];
		if ( (1<<(_log[i] + 1)) == i) _log[i]++;
	}
	cin >> s;
	int n = s.size();
	build_suffix_tree();
	findLongestPalindromicString();
	st = rmq(2*n+1);
	dfs(0, 0);
	memset (pai, -1, sizeof pai);
	for (int i = 1; i < at; i++) {
		int len = ac[i];
		int l = comeco[i];
		int r = comeco[i] + len - 1;
		//find longest palindrome in l r
		l = l * 2;
		r = r * 2 + 2;
		int lo = 0, hi = r-l+1, ans = 0;
		while (lo <= hi) {
			int mid = (lo + hi) / 2;
			int ql = l + mid, qr = r - mid;
			if (ql > qr) {
				hi = mid-1;
				continue;
			}
			int ret = st.query(ql, qr);
			if (ret >= mid) {
				ans = mid;
				lo = mid+1;
			} else hi = mid-1;
		}
		::ans = max(::ans, sz[i] * ll(ans));
	}

	cout << ans << endl;
	return 0;
}

Compilation message

palindrome.cpp: In function 'void build_suffix_tree()':
palindrome.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < s.size(); j++) {
                     ~~^~~~~~~~~~
palindrome.cpp: In function 'void findLongestPalindromicString()':
palindrome.cpp:100:9: warning: variable 'end' set but not used [-Wunused-but-set-variable]
     int end = -1;
         ^~~
palindrome.cpp: In function 'int novo(int, int, int)':
palindrome.cpp:10:8: warning: '<anonymous>.No::suff' is used uninitialized in this function [-Wuninitialized]
 struct No {
        ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 44408 KB Output is correct
2 Correct 41 ms 44540 KB Output is correct
3 Correct 41 ms 44540 KB Output is correct
4 Correct 40 ms 44540 KB Output is correct
5 Correct 41 ms 44568 KB Output is correct
6 Correct 41 ms 44568 KB Output is correct
7 Correct 41 ms 44568 KB Output is correct
8 Correct 42 ms 44584 KB Output is correct
9 Correct 40 ms 44584 KB Output is correct
10 Correct 40 ms 44596 KB Output is correct
11 Correct 41 ms 44596 KB Output is correct
12 Correct 42 ms 44612 KB Output is correct
13 Correct 40 ms 44612 KB Output is correct
14 Correct 41 ms 44612 KB Output is correct
15 Correct 42 ms 44612 KB Output is correct
16 Correct 41 ms 44612 KB Output is correct
17 Correct 41 ms 44612 KB Output is correct
18 Correct 40 ms 44612 KB Output is correct
19 Correct 40 ms 44612 KB Output is correct
20 Correct 43 ms 44612 KB Output is correct
21 Correct 43 ms 44612 KB Output is correct
22 Correct 42 ms 44612 KB Output is correct
23 Correct 40 ms 44612 KB Output is correct
24 Correct 40 ms 44740 KB Output is correct
25 Correct 41 ms 44740 KB Output is correct
26 Correct 39 ms 44752 KB Output is correct
27 Correct 40 ms 44752 KB Output is correct
28 Correct 40 ms 44752 KB Output is correct
29 Correct 39 ms 44752 KB Output is correct
30 Correct 42 ms 44752 KB Output is correct
31 Correct 42 ms 44752 KB Output is correct
32 Correct 39 ms 44752 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 44896 KB Output is correct
2 Correct 43 ms 44896 KB Output is correct
3 Correct 42 ms 45024 KB Output is correct
4 Correct 43 ms 45024 KB Output is correct
5 Correct 41 ms 45024 KB Output is correct
6 Correct 41 ms 45024 KB Output is correct
7 Correct 41 ms 45024 KB Output is correct
8 Correct 43 ms 45024 KB Output is correct
9 Correct 42 ms 45024 KB Output is correct
10 Correct 41 ms 45024 KB Output is correct
11 Correct 41 ms 45024 KB Output is correct
12 Correct 42 ms 45024 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47740 KB Output is correct
2 Correct 47 ms 47740 KB Output is correct
3 Correct 47 ms 47872 KB Output is correct
4 Correct 46 ms 47872 KB Output is correct
5 Correct 47 ms 47872 KB Output is correct
6 Correct 48 ms 47872 KB Output is correct
7 Correct 47 ms 47872 KB Output is correct
8 Correct 48 ms 47872 KB Output is correct
9 Correct 48 ms 47872 KB Output is correct
10 Correct 48 ms 47872 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 75772 KB Output is correct
2 Correct 139 ms 75772 KB Output is correct
3 Correct 123 ms 78268 KB Output is correct
4 Correct 117 ms 78268 KB Output is correct
5 Correct 144 ms 78268 KB Output is correct
6 Correct 139 ms 78268 KB Output is correct
7 Correct 121 ms 78268 KB Output is correct
8 Correct 167 ms 78268 KB Output is correct
9 Correct 153 ms 78268 KB Output is correct
10 Correct 153 ms 78268 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -