oj.uz

Submission #114076

# Submission time Handle Problem Language Result Execution time Memory
114076 2019-05-29T22:37:10 Z zoooma13 Rima (COCI17_rima) C++14
56 / 140
 740 ms 144836 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500005

int n;
string s[MAX_N];

int root ,nn;
int tr[27][10*MAX_N];
void add(int&p ,string&s ,int i=0){
    if(!p) p = ++nn;
    if(i == s.size()){
        tr[26][p]++;
        return;
    }
    add(tr[s[i]-'a'][p] ,s ,i+1);
}
int max_suf = 0;
int dfs(int&p){
    int all_end = 0;
    vector <int> ch(26) ,en(26);
    for(int c=0; c<26; c++) if(tr[c][p]){
        ch[c] = dfs(tr[c][p]);
        en[c] = tr[26][tr[c][p]];
        all_end += en[c];
    }
    if(!all_end)
        return 0;
    int mx = 0;
    for(int c=0; c<26; c++) if(en[c])
        mx = max(mx ,ch[c]);
    max_suf = max(max_suf ,mx+all_end);
    return mx+all_end;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> s[i];
        reverse(s[i].begin() ,s[i].end());
        add(root ,s[i]);
    }
    dfs(root);
    cout << max_suf << endl;
}

Compilation message

rima.cpp: In function 'void add(int&, std::__cxx11::string&, int)':
rima.cpp:13:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i == s.size()){
        ~~^~~~~~~~~~~

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16256 KB Output is correct
2 Correct 15 ms 16256 KB Output is correct
3 Correct 14 ms 16256 KB Output is correct
4 Incorrect 740 ms 83820 KB Output isn't correct
5 Correct 109 ms 23800 KB Output is correct
6 Incorrect 232 ms 137744 KB Output isn't correct
7 Incorrect 221 ms 137364 KB Output isn't correct
8 Incorrect 216 ms 137236 KB Output isn't correct
9 Incorrect 316 ms 144836 KB Output isn't correct
10 Incorrect 258 ms 137108 KB Output isn't correct