#pragma comment(linker, "/STACK: 3000000")
#include<bits/stdc++.h>
using namespace std ;
const int N = 3e6 + 7 ;
int n ;
string ss[N] ;
struct trie{
int nxt[N][27] ;
int cnt[N] ;
int t = 1 ;
int dp[N][2] ;
void add(string &add_ ){
int cur = 1 ;
int sz = add_.size() ;
for(int i = 0 ;i < sz ;i++ ){
int c = add_[i] - 'a' ;
if(!nxt[cur][c])nxt[cur][c] = ++t ;
cur = nxt[cur][c] ;
}
cnt[cur] ++ ;
}
int solve(int i , bool flag){
if(dp[i][flag]!=-1) return dp[i][flag] ;
if(flag && !cnt[i]) return 0 ;
int ret = 0 ;
int kids = 0 ;
for(int j = 0 ;j < 26 ;j ++){
kids +=cnt[nxt[i][j]] ;
}
vector<int> res = {0 , 0};
for(int j = 0 ;j < 26 ; j++){
if(nxt[i][j]){
ret = max(ret , solve(nxt[i][j] , flag ) ) ;
ret = max(ret , solve(nxt[i][j] , 1) + kids ) ;
res.push_back(solve(nxt[i][j] , 1) + kids) ;
}
}
sort(res.begin() , res.end()) ;
ret = max(ret , res.back() + res[res.size()-2] - kids ) ;
return dp[i][flag] =ret ;
}
} tr;
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
memset(tr.dp , -1 , sizeof tr.dp) ;
cin>>n ;
for(int i = 0 ; i < n ;i++){
string x ;
cin>>x ;
reverse( x .begin() , x.end()) ;
tr.add(x) ;
}
int ans = max(tr.solve(1 , 0 ) , tr.solve(1 , 1)) ;
cout<< ans;
return 0 ;
}
Compilation message
rima.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK: 3000000")
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
68 ms |
117880 KB |
Output is correct |
| 2 |
Correct |
69 ms |
117880 KB |
Output is correct |
| 3 |
Correct |
69 ms |
117880 KB |
Output is correct |
| 4 |
Incorrect |
448 ms |
185080 KB |
Output isn't correct |
| 5 |
Correct |
89 ms |
118520 KB |
Output is correct |
| 6 |
Incorrect |
173 ms |
215512 KB |
Output isn't correct |
| 7 |
Incorrect |
166 ms |
215468 KB |
Output isn't correct |
| 8 |
Incorrect |
167 ms |
215324 KB |
Output isn't correct |
| 9 |
Incorrect |
198 ms |
216820 KB |
Output isn't correct |
| 10 |
Incorrect |
177 ms |
215372 KB |
Output isn't correct |
