제출 #718255

#제출 시각아이디문제언어결과실행 시간메모리
718255Ahmed57Rima (COCI17_rima)C++14
140 / 140
313 ms239876 KiB
#include <bits/stdc++.h> using namespace std ; //TRIE struct node{ node *nxt[26]; int is = 0; node(){ is = 0; for(int i = 0;i<26;i++){ nxt[i] = NULL; } } }; void inser(string w,node *root){ for(auto ch:w){ if(root->nxt[ch-'a']==NULL){ root->nxt[ch-'a'] = new node(); } root=root->nxt[ch-'a']; } root->is++; } int Nnode = 0; vector<int> adj[3000001]; int mark[3000001]; void build(node *root){ int cur = Nnode; for(int j = 0;j<26;j++){ if(root->nxt[j]!=NULL){ Nnode++; adj[cur].push_back(Nnode); mark[Nnode] = root->nxt[j]->is; build(root->nxt[j]); } } } long long dp[3000001]; long long calc(int node){ if(dp[node]!=-1)return dp[node]; long long ma = 0 , sum = 0; for(auto j:adj[node]){ sum+=mark[j]; } for(auto j:adj[node]){ if(mark[j]>0){ ma = max(ma,calc(j)); } } return dp[node]=ma+sum; } long long ge(int node){ long long sum = mark[node]; for(auto j:adj[node]){ sum+=mark[j]; } long long ma1 = 0 , ma2 = 0; for(auto j:adj[node]){ if(mark[j]){ if(ma1<=calc(j)){ ma2 = ma1; ma1 = calc(j); }else if(ma2<calc(j)){ ma2 = calc(j); } } } return sum+ma1+ma2; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; node *root = new node(); while(n--){ string s;cin>>s; reverse(s.begin(),s.end()); inser(s,root); } build(root); memset(dp,-1,sizeof dp); long long all =calc(0); for(int i = 0;i<=Nnode;i++){ all = max(all,ge(i)); } cout<<all<<endl; return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...