oj.uz

Submission #994049

# Submission time Handle Problem Language Result Execution time Memory
994049 2024-06-07T05:05:13 Z vjudge1 Rima (COCI17_rima) C++17
42 / 140
 1000 ms 57900 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 440 KB Output is correct
4 Execution timed out 1097 ms 57900 KB Time limit exceeded
5 Correct 64 ms 6736 KB Output is correct
6 Incorrect 17 ms 2516 KB Output isn't correct
7 Incorrect 14 ms 2240 KB Output isn't correct
8 Incorrect 12 ms 2060 KB Output isn't correct
9 Incorrect 109 ms 8344 KB Output isn't correct
10 Incorrect 11 ms 2000 KB Output isn't correct