Submission #114077

#	Time	Username	Problem	Language	Result	Execution time	Memory
114077		zoooma13	Rima (COCI17_rima)	C++14	56 / 140	622 ms	81144 KiB

rima

#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 ch ,mx_ch = 0 ,all_en = 0;
    for(int c=0; c<26; c++) if(tr[c][p]){
        ch = dfs(tr[c][p]);
        if(tr[26][tr[c][p]])
            mx_ch = max(mx_ch ,ch);
        all_en +=  tr[26][tr[c][p]];
    }

    max_suf = max(max_suf ,mx_ch+all_en);
    return (all_en ? mx_ch+all_en : 0);
}

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 (stderr)

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 / 140