oj.uz

Submission #77007

# Submission time Handle Problem Language Result Execution time Memory
77007 2018-09-20T04:19:58 Z samuelfgs96 Palindromes (APIO14_palindrome) C++11
73 / 100
 373 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();
	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 {
	int table[N*2][LN], n;
	rmq () { }
	rmq (int n) : n(n) {
		for (int i = 0; i < n; i++) {
			table[i][0] = L[i];
		}
		for (int j = 1; (1<<j) <= n; j++)
		for (int i = 0; i + (1<<j) <= n; i++)
			table[i][j] = max(table[i][j-1], table[i+(1<<(j-1))][j-1]);
	}
	int query (int l, int r) {
		int sz = r - l + 1;
		int lg = _log[sz];
		return max(table[l][lg], table[r - (1<<lg) + 1][lg]);
	}
} st;

ll ans = 0;
void solve (int u, ll len) {
	len += t[u].len();
	if (len) {
		int l = comeco[u];
		int r = comeco[u] + 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[u] * ll(ans));
	}
	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);
	solve(0, 0);
	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 94 ms 93432 KB Output is correct
2 Correct 105 ms 93588 KB Output is correct
3 Correct 99 ms 93588 KB Output is correct
4 Correct 97 ms 93588 KB Output is correct
5 Correct 113 ms 93616 KB Output is correct
6 Correct 101 ms 93616 KB Output is correct
7 Correct 98 ms 93616 KB Output is correct
8 Correct 101 ms 93660 KB Output is correct
9 Correct 95 ms 93660 KB Output is correct
10 Correct 101 ms 93660 KB Output is correct
11 Correct 98 ms 93684 KB Output is correct
12 Correct 98 ms 93684 KB Output is correct
13 Correct 99 ms 93684 KB Output is correct
14 Correct 97 ms 93700 KB Output is correct
15 Correct 97 ms 93700 KB Output is correct
16 Correct 98 ms 93700 KB Output is correct
17 Correct 98 ms 93888 KB Output is correct
18 Correct 94 ms 93888 KB Output is correct
19 Correct 99 ms 93888 KB Output is correct
20 Correct 97 ms 93888 KB Output is correct
21 Correct 97 ms 93888 KB Output is correct
22 Correct 94 ms 93888 KB Output is correct
23 Correct 100 ms 93888 KB Output is correct
24 Correct 95 ms 93888 KB Output is correct
25 Correct 102 ms 93888 KB Output is correct
26 Correct 95 ms 93908 KB Output is correct
27 Correct 103 ms 93908 KB Output is correct
28 Correct 97 ms 93908 KB Output is correct
29 Correct 98 ms 93908 KB Output is correct
30 Correct 98 ms 93908 KB Output is correct
31 Correct 98 ms 93908 KB Output is correct
32 Correct 99 ms 93908 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 94080 KB Output is correct
2 Correct 98 ms 94080 KB Output is correct
3 Correct 102 ms 94120 KB Output is correct
4 Correct 100 ms 94124 KB Output is correct
5 Correct 98 ms 94384 KB Output is correct
6 Correct 98 ms 94384 KB Output is correct
7 Correct 101 ms 94384 KB Output is correct
8 Correct 96 ms 94384 KB Output is correct
9 Correct 98 ms 94384 KB Output is correct
10 Correct 95 ms 94384 KB Output is correct
11 Correct 96 ms 94384 KB Output is correct
12 Correct 95 ms 94384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 97040 KB Output is correct
2 Correct 104 ms 97040 KB Output is correct
3 Correct 103 ms 97320 KB Output is correct
4 Correct 104 ms 97320 KB Output is correct
5 Correct 108 ms 97320 KB Output is correct
6 Correct 106 ms 97320 KB Output is correct
7 Correct 102 ms 97320 KB Output is correct
8 Correct 121 ms 97320 KB Output is correct
9 Correct 108 ms 97320 KB Output is correct
10 Correct 115 ms 97320 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 125324 KB Output is correct
2 Correct 234 ms 125324 KB Output is correct
3 Correct 197 ms 128580 KB Output is correct
4 Correct 219 ms 128580 KB Output is correct
5 Correct 358 ms 128580 KB Output is correct
6 Correct 287 ms 128580 KB Output is correct
7 Correct 229 ms 128580 KB Output is correct
8 Correct 314 ms 128580 KB Output is correct
9 Correct 297 ms 128580 KB Output is correct
10 Correct 373 ms 128580 KB Output is correct

Subtask #5
0 / 27.0

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