oj.uz

Submission #114081

# Submission time Handle Problem Language Result Execution time Memory
114081 2019-05-30T00:54:20 Z zoooma13 Rima (COCI17_rima) C++14
140 / 140
 564 ms 65528 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500005
#define MAX_S 3000006

int n;
string s;

int root ,nn;
int tr[27][MAX_S];
void add(int&p ,int i=0){
    if(!p) p = ++nn;
    if(i == s.size()){
        tr[26][p]++;
        return;
    }
    add(tr[s[i]-'a'][p] ,i+1);
}
int max_suf = 0;
int dfs(int&p){
    int ch ,frst_mx_ch = 0 ,scnd_mx_ch = 0 ,all_en = 0;
    for(int c=0; c<26; c++) if(tr[c][p])
    {
        ch = dfs(tr[c][p]);
        all_en += tr[26][tr[c][p]];
        if(tr[26][tr[c][p]])
        {
            if(frst_mx_ch < ch){
                scnd_mx_ch = frst_mx_ch;
                frst_mx_ch = ch;
            }
            else if(scnd_mx_ch < ch){
                scnd_mx_ch = ch;
            }
        }
    }
    max_suf = max(max_suf ,frst_mx_ch+scnd_mx_ch+all_en+tr[26][p]);
    return frst_mx_ch+all_en;
}

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

    dfs(root);
    cout << max_suf << endl;
}

Compilation message

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 564 ms 65528 KB Output is correct
5 Correct 85 ms 632 KB Output is correct
6 Correct 102 ms 50580 KB Output is correct
7 Correct 99 ms 50452 KB Output is correct
8 Correct 96 ms 50452 KB Output is correct
9 Correct 179 ms 51896 KB Output is correct
10 Correct 98 ms 50600 KB Output is correct