Submission #718240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
718240	2023-04-03T17:38:34 Z	Ahmed57	Rima (COCI17_rima)	C++14	42 / 140	367 ms	262144 KB

rima

#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][2];
long long calc(int node,int ch){
    if(dp[node][ch]!=-1)return dp[node][ch];
    long long ma = 0 , sum = 0;
    for(auto j:adj[node]){
        sum+=mark[j];
    }
    if(ch==1){
        long long su = 0;
        for(auto j:adj[node]){
            if(mark[j]>1)su+=calc(j,1);
        }
        return dp[node][ch] = su+sum;
    }
    long long su = 0;
    for(auto j:adj[node]){
        if(mark[j]>1){
            su +=calc(j,1);
        }
    }
    for(auto j:adj[node]){
        if(mark[j]==1){
            ma = max(ma,calc(j,0)+su);
        }else{
            ma = max(ma,calc(j,0)+(su-calc(j,1)));
        }
    }
    return dp[node][ch]=ma+sum;
}
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 =0;
    for(int i = 0;i<=Nnode;i++){
        all = max(all,calc(i,0)+mark[i]);
    }
    cout<<all<<endl;
    return 0 ;
}

Subtask #1

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	117772 KB	Output is correct
2	Correct	60 ms	117740 KB	Output is correct
3	Correct	58 ms	117804 KB	Output is correct
4	Runtime error	367 ms	262144 KB	Execution killed with signal 9
5	Incorrect	68 ms	118636 KB	Output isn't correct
6	Incorrect	150 ms	227560 KB	Output isn't correct
7	Incorrect	151 ms	227416 KB	Output isn't correct
8	Incorrect	152 ms	227300 KB	Output isn't correct
9	Incorrect	153 ms	230700 KB	Output isn't correct
10	Incorrect	170 ms	227268 KB	Output isn't correct