oj.uz

Submission #228046

# Submission time Handle Problem Language Result Execution time Memory
228046 2020-04-29T17:08:36 Z MohamedAhmed04 Rima (COCI17_rima) C++14
28 / 140
 1000 ms 64120 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 16000 KB Output isn't correct
2 Correct 12 ms 16000 KB Output is correct
3 Incorrect 12 ms 16000 KB Output isn't correct
4 Execution timed out 1093 ms 64120 KB Time limit exceeded
5 Correct 37 ms 25080 KB Output is correct
6 Incorrect 20 ms 18968 KB Output isn't correct
7 Incorrect 19 ms 18596 KB Output isn't correct
8 Incorrect 20 ms 18268 KB Output isn't correct
9 Incorrect 72 ms 27604 KB Output isn't correct
10 Incorrect 18 ms 18308 KB Output isn't correct