oj.uz

답안 #47977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
47977 2018-05-09T09:49:19 Z Kmcode 회문 (APIO14_palindrome) C++14
0 / 100
 36 ms 36768 KB 
#include "bits/stdc++.h"
using namespace std;

#define MAX 300015
char buf[MAX];
string s;

int len[MAX];
int linkk[MAX];
int nex[MAX][26];

int ord;
int cur;

int cnt[MAX];

void append(int idx) {
	char c = s[idx];
	while (!(idx-len[cur]-1>=0&&s[idx]==s[idx-len[cur]-1])) {
		cur = linkk[cur];
	}
	if (nex[cur][c - 'a'] == -1) {
		nex[cur][c - 'a'] = ord;
		ord++;
	}
	len[nex[cur][c - 'a']] = len[cur] + 2;
	linkk[nex[cur][c - 'a']] = linkk[cur];
	cur = nex[cur][c - 'a'];
	while (linkk[cur] != -1&&nex[linkk[cur]][c-'a']==-1) {
		linkk[cur] = linkk[linkk[cur]];
	}
	if (linkk[cur] != -1) {
		linkk[cur] = nex[linkk[cur]][c - 'a'];
	}
	else {
		linkk[cur] = 1;
	}
	cnt[cur]++;
}

int main() {
	memset(nex, -1,sizeof(nex) );
	len[0] = -1;
	len[1] = 0;
	ord = 2;
	scanf("%s", buf);
	s = buf;
	linkk[1] = 0;
	linkk[0] = -1;
	for (int i = 0; i < s.size(); i++) {
		append(i);
	}
	long long int ans = 0;
	for (int i = ord - 1; i >= 0; i--) {
		cnt[linkk[i]] += cnt[i];
		ans = max(ans, (long long int)(len[i])*cnt[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) {
                  ~~^~~~~~~~~~
palindrome.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", buf);
  ~~~~~^~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 30840 KB Output is correct
2 Correct 24 ms 30952 KB Output is correct
3 Correct 24 ms 30952 KB Output is correct
4 Correct 24 ms 30952 KB Output is correct
5 Correct 24 ms 30980 KB Output is correct
6 Correct 24 ms 31160 KB Output is correct
7 Correct 24 ms 31160 KB Output is correct
8 Correct 23 ms 31160 KB Output is correct
9 Correct 24 ms 31160 KB Output is correct
10 Incorrect 24 ms 31160 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 31160 KB Output is correct
2 Correct 24 ms 31160 KB Output is correct
3 Correct 24 ms 31160 KB Output is correct
4 Correct 24 ms 31160 KB Output is correct
5 Correct 23 ms 31160 KB Output is correct
6 Correct 26 ms 31160 KB Output is correct
7 Correct 24 ms 31180 KB Output is correct
8 Correct 24 ms 31180 KB Output is correct
9 Correct 24 ms 31180 KB Output is correct
10 Correct 24 ms 31180 KB Output is correct
11 Correct 24 ms 31180 KB Output is correct
12 Incorrect 24 ms 31180 KB Output isn't correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 31332 KB Output is correct
2 Correct 25 ms 31332 KB Output is correct
3 Correct 24 ms 31332 KB Output is correct
4 Correct 24 ms 31332 KB Output is correct
5 Correct 24 ms 31332 KB Output is correct
6 Correct 23 ms 31332 KB Output is correct
7 Correct 24 ms 31356 KB Output is correct
8 Incorrect 24 ms 31356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 32480 KB Output is correct
2 Correct 28 ms 32508 KB Output is correct
3 Correct 28 ms 32508 KB Output is correct
4 Correct 28 ms 32508 KB Output is correct
5 Correct 28 ms 32600 KB Output is correct
6 Correct 27 ms 32600 KB Output is correct
7 Correct 27 ms 32600 KB Output is correct
8 Incorrect 26 ms 32600 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 35196 KB Output is correct
2 Correct 36 ms 35712 KB Output is correct
3 Correct 35 ms 36132 KB Output is correct
4 Correct 36 ms 36264 KB Output is correct
5 Correct 36 ms 36620 KB Output is correct
6 Correct 35 ms 36620 KB Output is correct
7 Correct 35 ms 36768 KB Output is correct
8 Incorrect 29 ms 36768 KB Output isn't correct
9 Halted 0 ms 0 KB -