#include <bits/stdc++.h>
using namespace std ;
const int MAX = 5e5 + 10 ;
string arr[MAX] ;
int n ;
int tree[MAX][27] , Cnt[MAX*27] ;
int last = 0 ;
void Insert(string s)
{
int node = 0 ;
for(int i = 0 ; i < s.size() ; ++i)
{
if(i == s.size()-1)
Cnt[node]++ ;
char c = s[i] ;
int idx = c - 'a' ;
if(!tree[node][idx])
tree[node][idx] = ++last ;
node = tree[node][idx] ;
}
}
int query(string s)
{
int node = 0 , cnt = Cnt[0] ;
for(int i = 0 ; i < s.size() ; ++i)
{
char c = s[i] ;
int idx = c - 'a' ;
if(!tree[node][idx])
return 0 ;
node = tree[node][idx] ;
if(!Cnt[node] && i != s.size()-1)
cnt = 0 ;
else
cnt += Cnt[node] ;
}
return cnt ;
}
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) ;
int ans = 0 ;
for(int i = 0 ; i < n ; ++i)
{
string s = arr[i].substr(0 , arr[i].size()-1) ;
ans = max(ans , query(s)+1) ;
Insert(arr[i]) ;
}
return cout<<ans<<"\n" , 0 ;
}
Compilation message
rima.cpp: In function 'void Insert(std::__cxx11::string)':
rima.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < s.size() ; ++i)
~~^~~~~~~~~~
rima.cpp:18:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == s.size()-1)
~~^~~~~~~~~~~~~
rima.cpp: In function 'int query(std::__cxx11::string)':
rima.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < s.size() ; ++i)
~~^~~~~~~~~~
rima.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(!Cnt[node] && i != s.size()-1)
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
13 ms |
16000 KB |
Output is correct |
| 3 |
Correct |
14 ms |
16128 KB |
Output is correct |
| 4 |
Runtime error |
374 ms |
144760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Correct |
48 ms |
19968 KB |
Output is correct |
| 6 |
Incorrect |
42 ms |
49768 KB |
Output isn't correct |
| 7 |
Incorrect |
40 ms |
49648 KB |
Output isn't correct |
| 8 |
Incorrect |
40 ms |
49324 KB |
Output isn't correct |
| 9 |
Incorrect |
90 ms |
53940 KB |
Output isn't correct |
| 10 |
Incorrect |
39 ms |
49364 KB |
Output isn't correct |
