답안 #49512 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49512	2018-05-30T06:29:18 Z	hamzqq9	회문 (APIO14_palindrome)	C++14	100 / 100	78 ms	40444 KB

palindrome

#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000000
#define inf 1000000005
#define N 300005
#define LOG 20
#define magic 100
#define KOK 250
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

int tot=2,n,now;
int nxt[N][26],link[N],lazy[N],len[N];
char s[N];
ll ans;
stack<int> stc;

void add(int ind) {

	while(s[ind-len[now]-1]!=s[ind]) now=link[now];

	if(nxt[now][s[ind]-'a']) {

		now=nxt[now][s[ind]-'a'];
		lazy[now]++;

		return ;

	} 

	int nw=++tot;	

	nxt[now][s[ind]-'a']=nw;

	len[nw]=len[now]+2;

	stc.push(nw);

	lazy[nw]++;

	if(len[nw]==1) {

		link[nw]=2;

		now=nw;

		return ;

	}

	now=link[now];

	while(s[ind-len[now]-1]!=s[ind]) now=link[now];

	link[nw]=nxt[now][s[ind]-'a'];

	now=nw;

}

int main() {
 
 	#if 0
	freopen("input.txt","r",stdin);
 	#endif

	scanf("%s",s+1);

	n=strlen(s+1);

	link[1]=1;link[2]=1;
	len[1]=-1;len[2]=0;
	now=1;

	for(int i=1;i<=n;i++) add(i);

	while(!stc.empty()) {

		int x=stc.top();

		stc.pop();

		ans=max(ans,1ll*len[x]*lazy[x]);

		lazy[link[x]]+=lazy[x];

	}

	printf("%lld",ans);

}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	2 ms	448 KB	Output is correct
4	Correct	2 ms	480 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	2 ms	656 KB	Output is correct
7	Correct	2 ms	656 KB	Output is correct
8	Correct	2 ms	656 KB	Output is correct
9	Correct	2 ms	656 KB	Output is correct
10	Correct	2 ms	656 KB	Output is correct
11	Correct	2 ms	656 KB	Output is correct
12	Correct	2 ms	672 KB	Output is correct
13	Correct	2 ms	676 KB	Output is correct
14	Correct	2 ms	680 KB	Output is correct
15	Correct	2 ms	684 KB	Output is correct
16	Correct	2 ms	688 KB	Output is correct
17	Correct	2 ms	692 KB	Output is correct
18	Correct	2 ms	696 KB	Output is correct
19	Correct	2 ms	700 KB	Output is correct
20	Correct	2 ms	704 KB	Output is correct
21	Correct	2 ms	708 KB	Output is correct
22	Correct	2 ms	716 KB	Output is correct
23	Correct	2 ms	720 KB	Output is correct
24	Correct	2 ms	724 KB	Output is correct
25	Correct	2 ms	728 KB	Output is correct
26	Correct	6 ms	764 KB	Output is correct
27	Correct	2 ms	764 KB	Output is correct
28	Correct	2 ms	764 KB	Output is correct
29	Correct	2 ms	776 KB	Output is correct
30	Correct	7 ms	780 KB	Output is correct
31	Correct	2 ms	784 KB	Output is correct
32	Correct	2 ms	788 KB	Output is correct

Subtask #2
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	952 KB	Output is correct
2	Correct	2 ms	952 KB	Output is correct
3	Correct	2 ms	956 KB	Output is correct
4	Correct	3 ms	960 KB	Output is correct
5	Correct	2 ms	964 KB	Output is correct
6	Correct	2 ms	964 KB	Output is correct
7	Correct	2 ms	972 KB	Output is correct
8	Correct	2 ms	976 KB	Output is correct
9	Correct	2 ms	976 KB	Output is correct
10	Correct	3 ms	976 KB	Output is correct
11	Correct	2 ms	976 KB	Output is correct
12	Correct	2 ms	976 KB	Output is correct

Subtask #3
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2020 KB	Output is correct
2	Correct	3 ms	2020 KB	Output is correct
3	Correct	4 ms	2032 KB	Output is correct
4	Correct	4 ms	2060 KB	Output is correct
5	Correct	4 ms	2088 KB	Output is correct
6	Correct	4 ms	2100 KB	Output is correct
7	Correct	4 ms	2112 KB	Output is correct
8	Correct	3 ms	2112 KB	Output is correct
9	Correct	2 ms	2112 KB	Output is correct
10	Correct	4 ms	2112 KB	Output is correct

Subtask #4
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	12800 KB	Output is correct
2	Correct	17 ms	12932 KB	Output is correct
3	Correct	20 ms	13028 KB	Output is correct
4	Correct	17 ms	13128 KB	Output is correct
5	Correct	21 ms	13228 KB	Output is correct
6	Correct	14 ms	13228 KB	Output is correct
7	Correct	17 ms	13228 KB	Output is correct
8	Correct	5 ms	13228 KB	Output is correct
9	Correct	7 ms	13228 KB	Output is correct
10	Correct	16 ms	13228 KB	Output is correct

Subtask #5
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	37464 KB	Output is correct
2	Correct	51 ms	37740 KB	Output is correct
3	Correct	43 ms	38076 KB	Output is correct
4	Correct	51 ms	38372 KB	Output is correct
5	Correct	78 ms	38668 KB	Output is correct
6	Correct	46 ms	38668 KB	Output is correct
7	Correct	45 ms	38668 KB	Output is correct
8	Correct	8 ms	38668 KB	Output is correct
9	Correct	7 ms	38668 KB	Output is correct
10	Correct	48 ms	38668 KB	Output is correct
11	Correct	43 ms	40444 KB	Output is correct
12	Correct	10 ms	40444 KB	Output is correct

답안 #49512

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 15.0 / 15.0

Subtask #3 24.0 / 24.0

Subtask #4 26.0 / 26.0

Subtask #5 27.0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
15.0 / 15.0

Subtask #3
24.0 / 24.0

Subtask #4
26.0 / 26.0

Subtask #5
27.0 / 27.0