oj.uz

Submission #77019

# Submission time Handle Problem Language Result Execution time Memory
77019 2018-09-20T04:40:43 Z samuelfgs96 Palindromes (APIO14_palindrome) C++11
73 / 100
 404 ms 106876 KB 
#include <bits/stdc++.h>
#define pb push_back
#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]);
    }
};
vector <No> t;
int novo (int L, int R, int p) {
	t.pb( 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();
	dfs(0, 0);
	t.clear();
	st = rmq(2*n+1);
	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:37: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:101: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' may be used uninitialized in this function [-Wmaybe-uninitialized]
 struct No {
        ^~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8936 KB Output is correct
2 Correct 15 ms 8936 KB Output is correct
3 Correct 16 ms 9192 KB Output is correct
4 Correct 17 ms 9192 KB Output is correct
5 Correct 21 ms 9192 KB Output is correct
6 Correct 15 ms 9192 KB Output is correct
7 Correct 16 ms 9192 KB Output is correct
8 Correct 15 ms 9192 KB Output is correct
9 Correct 16 ms 9192 KB Output is correct
10 Correct 17 ms 9192 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 39816 KB Output is correct
2 Correct 115 ms 39816 KB Output is correct
3 Correct 100 ms 42048 KB Output is correct
4 Correct 96 ms 42048 KB Output is correct
5 Correct 128 ms 42048 KB Output is correct
6 Correct 136 ms 42048 KB Output is correct
7 Correct 97 ms 42048 KB Output is correct
8 Correct 149 ms 42048 KB Output is correct
9 Correct 154 ms 42048 KB Output is correct
10 Correct 176 ms 42048 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 106876 KB Output is correct
2 Incorrect 404 ms 106876 KB Output isn't correct
3 Halted 0 ms 0 KB -