oj.uz

Submission #111219

# Submission time Handle Problem Language Result Execution time Memory
111219 2019-05-14T09:30:45 Z user202729 Palindromes (APIO14_palindrome) C++17
100 / 100
 100 ms 61076 KB 
#include<iostream>
#include<array>
#include<cassert>
#include<vector>

struct PalinTree{
	static int constexpr MIN='a',CNT=26;
	using Idx=int;

	static Idx constexpr NONE=-1;

	struct Node{
		std::array<Idx,CNT> c; // children
		Idx link; // suffix link
		int len;

		// will be used to store number of occurences in the string
		int cnt;

		Node():link(0x12345678),len(0x12345678),cnt(0){
			for(Idx& i:c)i=NONE;
		}
	};

	std::vector<Node> d;
	static Idx constexpr ZERO=0, // node coer to emt string
			   NEG=1; // node coer to the "len = -1" string

	template<class Fn>
	Idx newnode(Fn f){
		auto n=(Idx)d.size();
		d.push_back({});
		f(d.back());
		return n;
	}

	template<class Fn>
	Idx child(Idx a,char c,
			Fn f // used in case a new node is constructed
			// void(Node&)
			){
		c-=MIN;
		if(d[a].c[c]<0){
			Idx ans=newnode(f);
			d[a].c[c]=ans;
			return ans;
		}
		return d[a].c[c];
	}

	// std::string s;
	PalinTree(std::string const s):
		d(2)
		// ,s(std::move(_s))
	{
		d[ZERO].link=NEG;
		d[ZERO].len=0;
		d[NEG].len=-1;

		Idx n=ZERO; // current node
		for(unsigned i=0;i<s.size();++i){
			char c=s[i];
			while(true){
				int j=i-d[n].len;
				if(j!=0&&s[j-1]==c){
					int newlen=d[n].len+2;
					Idx oldlink=d[n].link;
					n=child(n,c,[&](Node& z){
							z.len=newlen;
							if(newlen==1)
								z.link=ZERO;
							else{
								Idx l=oldlink;
								while(c!=s[i-d[l].len-1])
									l=d[l].link;
								z.link=d[l].c[c-MIN];
								assert(z.link!=NONE);
							}
							});
					break;
				}
				n=d[n].link;
			}
			++d[n].cnt;
		}

		// accumulate cnt by link edge
		std::vector<Idx> ns; // list of nodes sorted by order
		ns.reserve(d.size());
		ns.push_back((Idx)NEG);
		ns.push_back((Idx)ZERO);
		for(unsigned i=0;i<d.size();++i){
			for(Idx c:d[ns[i]].c)
				if(c>=0)
					ns.push_back(c);
		}
		assert(ns.size()==d.size());

		for(unsigned i=d.size()-1;i;--i){
			int n=ns[i];
			d[d[n].link].cnt+=d[n].cnt;
		}
	}
};

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	std::string s;std::cin>>s;
	PalinTree t(s);
	int64_t ans=0;
	for(unsigned i=2;i<t.d.size();++i)
		ans=std::max(ans,(int64_t)t.d[i].len*t.d[i].cnt);
	std::cout<<ans<<'\n';
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 4 ms 552 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2524 KB Output is correct
2 Correct 5 ms 2368 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 6 ms 2396 KB Output is correct
7 Correct 5 ms 2396 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 1456 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 15868 KB Output is correct
2 Correct 24 ms 15740 KB Output is correct
3 Correct 28 ms 15740 KB Output is correct
4 Correct 26 ms 15732 KB Output is correct
5 Correct 27 ms 15752 KB Output is correct
6 Correct 22 ms 15728 KB Output is correct
7 Correct 23 ms 15732 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 10 ms 4548 KB Output is correct
10 Correct 29 ms 15724 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 61076 KB Output is correct
2 Correct 95 ms 60876 KB Output is correct
3 Correct 90 ms 60848 KB Output is correct
4 Correct 87 ms 60852 KB Output is correct
5 Correct 100 ms 60856 KB Output is correct
6 Correct 99 ms 61016 KB Output is correct
7 Correct 65 ms 31204 KB Output is correct
8 Correct 8 ms 1672 KB Output is correct
9 Correct 8 ms 1672 KB Output is correct
10 Correct 64 ms 31200 KB Output is correct
11 Correct 86 ms 60972 KB Output is correct
12 Correct 12 ms 5056 KB Output is correct