oj.uz

답안 #77645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77645 2018-09-29T09:28:10 Z samuelfgs96 회문 (APIO14_palindrome) C++11
0 / 100
 72 ms 56096 KB 
#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

using namespace std;

const int N = 212345;
typedef pair<int, int> pii;
typedef long long ll;
 
int bit[N];
struct treez {
	struct Node { 
		int start, end; 
		int length; 
		int insertEdg[26]; 
		int suffixEdg; 
		int qtd;
	}; 
	Node root1, root2; 
	Node tree[N]; 
	int currNode; 
	string s; 
	int ptr; 
	treez () { }
	treez (string s) : s(s) { 
		root1.length = -1; 
		root1.suffixEdg = 1; 
		root2.length = 0; 
		root2.suffixEdg = 1; 
		memset (tree, 0, sizeof tree);
		tree[1] = root1; 
		tree[2] = root2; 
		ptr = 2; 
		currNode = 1; 
		for (int i = 0; i < s.size(); i++) insert(i);
	}
	  
	void insert(int idx) { 
		int tmp = currNode;
		while (true) { 
			int curLength = tree[tmp].length; 
			if (idx - curLength >= 1 and s[idx] == s[idx-curLength-1]) 
				break; 
			tmp = tree[tmp].suffixEdg; 
		} 
	  
		if(tree[tmp].insertEdg[s[idx]-'a'] != 0) { 
			currNode = tree[tmp].insertEdg[s[idx]-'a']; 
			cout << idx << " ";
			for (int j = tree[currNode].start; j <= tree[currNode].end; j++)
				cout << s[j];
			cout << endl;
			tree[currNode].qtd++;
			return; 
		} 
		ptr++; 
		tree[tmp].insertEdg[s[idx]-'a'] = ptr; 
		tree[ptr].length = tree[tmp].length + 2; 
		tree[ptr].end = idx; 
		tree[ptr].start = idx - tree[ptr].length + 1; 
		tree[ptr].qtd = 1;
	  
		tmp = tree[tmp].suffixEdg; 
		currNode = ptr; 
		if (tree[currNode].length == 1) { 
			tree[currNode].suffixEdg = 2; 
			return; 
		} 
		while (true) { 
			int curLength = tree[tmp].length; 
			if (idx-curLength >= 1 and s[idx] == s[idx-curLength-1]) 
				break; 
			tmp = tree[tmp].suffixEdg; 
		} 
	  
		tree[currNode].suffixEdg = tree[tmp].insertEdg[s[idx]-'a']; 
	} 
};
treez t1;
string s;
ll ans;
int dfs (int u, int sz) {
	for (int i = 0; i < 26; i++)
		if (t1.tree[u].insertEdg[i])
			dfs(t1.tree[u].insertEdg[i], t1.tree[u].qtd);
	if (u >= 3) 
		ans = max(ans, ll(sz) * (t1.tree[u].end - t1.tree[u].start + 1));
	return sz;
}
int main (void) {
	cin >> s;
	t1 = treez(s);
	dfs(1, 0);
	dfs(2, 0);
	cout << ans << endl;
	return 0;
}

Compilation message

palindrome.cpp: In constructor 'treez::treez(std::__cxx11::string)':
palindrome.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < s.size(); i++) insert(i);
                   ~~^~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 51832 KB Output is correct
2 Incorrect 49 ms 52096 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 52216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 50 ms 52796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 56096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 72 ms 56096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -