Submission #228046

#	Time	Username	Problem	Language	Result	Execution time	Memory
228046		MohamedAhmed04	Rima (COCI17_rima)	C++14	28 / 140	1093 ms	64120 KiB

rima

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 5e5 + 10 ;

string arr[MAX] ;
int n ;

bool cmp(string &a , string &b)
{
	if(a.size() == b.size())
		return a < b ;
	else
		return a.size() < b.size() ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>arr[i] ;
		reverse(arr[i].begin() , arr[i].end()) ;
	}
	sort(arr , arr + n , cmp) ;
	map<string , int>dp ;
	dp[""] = 0 ;
	int ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		string a = arr[i]; 
		string b = arr[i].substr(0 , arr[i].size()-1) ;
		int x = 1 ;
		if(dp.find(a) != dp.end())
			x = max(x , dp[a]+1) ;
		if(dp.find(b) != dp.end())
			x = max(x , dp[b]+1) ;
		dp[a] = dp[b] = x ;
		ans = max(ans , dp[a]) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

• Subtask 1: 28 / 140