oj.uz

Submission #229554

# Submission time Handle Problem Language Result Execution time Memory
229554 2020-05-05T05:00:26 Z Uzumaki_Naturoo Rima (COCI17_rima) C++14
0 / 140
 137 ms 262148 KB 
/// You just can't beat the person who never gives up
/// ICPC next year

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 3e6+5 ;

int n ,m ;
char str[N] ;
int to[26][N] ,sz ;
bool en[N] ;
void insert_str(){
    int cur = 0 ;
    for(int i=0;i<m;++i){
        int cc = str[i] - 'a' ;
        if(to[cc][cur]==-1) to[cc][cur] = ++sz ;
        cur = to[cc][cur] ;
    }
    en[cur] = 1 ;
}
int mem[N][2] ;
int dfs(int cur,bool is){
    int&ret = mem[cur][is];
    if(~ret) return ret;
    ret = 0 ;
    if(!is){
        for(int i=0;i<26;++i) if(to[i][cur]!=-1) ret = max(ret ,dfs(to[i][cur],0)) ;
    }

    int here = 0 ;
    for(int i=0;i<26;++i) if(to[i][cur]!=-1) here += en[to[i][cur]] ;
    if(!here) return ret ;

    ret = max(ret,here) ;
    for(int i=0;i<26;++i) if(to[i][cur]!=-1 && en[to[i][cur]]) ret = max(ret ,here + dfs(to[i][cur],1)) ;
    return ret ;
}
int main(){
    memset(to,-1,sizeof to);
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%s",str);
        m = strlen(str) ;
        reverse(str,str+m);
        insert_str();
    }
    memset(mem,-1,sizeof mem);
    printf("%d",dfs(0,0));
    return 0;
}

Compilation message

rima.cpp: In function 'int main()':
rima.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
rima.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",str);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 129 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 133 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 135 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 131 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 128 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 132 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 134 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 137 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)