Submission #994049

#	Time	Username	Problem	Language	Result	Execution time	Memory
994049		vjudge1	Rima (COCI17_rima)	C++17	42 / 140	1097 ms	57900 KiB

rima

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int h = 727, mod = 1e9 + 7;
const int h1 = 369, mod1 = 998244353;

int power(int a,int b,int md)
{
	int ans=1;
	while (b)
	{
		if (b&1)
			ans=ans*a%md;
		a=a*a%md;
		b>>=1;
	}
	return ans;
}

signed main()
{
	int n;
	cin>>n;
	map<int,vector<string>> mp;
	for (int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		mp[s.size()].push_back(s);
	}
	vector<string> v;
	for (auto i:mp)
		for (auto j:i.second)
			v.push_back(j);
	reverse(v.begin(),v.end());
	map<pair<int,int>,int> ans;
	while (!v.empty())
	{
		string s=v.back();
		v.pop_back();
		int hs=0,hs1=0;
		for (int i=1;i<s.size();i++)
		{
			hs=hs*h+s[i],hs1=hs1*h1+s[i];
			hs%=mod,hs1%=mod1;
		}
		int mx;
		if (ans.find({hs,hs1})!=ans.end())
			mx=ans[{hs,hs1}]+1;
		else
			mx=1;
		for (int c='a';c<='z';c++)
		{
			pair<int,int> p={hs,hs1};
			p.first+=power(h,(int)s.size()-1,mod)*c%mod;
			p.second+=power(h1,(int)s.size()-1,mod1)*c%mod1;
			p.first%=mod,p.second%=mod1;
			if (ans.find(p)!=ans.end())
				mx=max(mx,ans[p]+1);
		}
		int c=s[0];
		pair<int,int> p={hs,hs1};
		p.first+=power(h,(int)s.size()-1,mod)*c%mod;
		p.second+=power(h1,(int)s.size()-1,mod1)*c%mod1;
		p.first%=mod,p.second%=mod1;
		ans[p]=mx;
	}
	int res=0;
	for (auto i:ans)
		res=max(res,i.second);
	cout<<res<<endl;
	
	return 0;
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:45:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i=1;i<s.size();i++)
      |                ~^~~~~~~~~

• Subtask 1: 42 / 140