Submission #99169

#	Time	Username	Problem	Language	Result	Execution time	Memory
99169		dalgerok	Rima (COCI17_rima)	C++17	126 / 140	1091 ms	186048 KiB

rima

#include<bits/stdc++.h>
using namespace std;


const int N = 5e5 + 5, M = 3e6 + 5;




int n, cnt[M], sz, dp[M], ans;
map < int, int > bor[M];
string s;


inline void Add(string &s){
    int v = 0;
    for(auto it : s){
        if(!bor[v][it]){
            bor[v][it] = ++sz;
        }
        v = bor[v][it];
    }
    cnt[v] += 1;
}

void dfs(int v){
    int mx1 = 0, mx2 = 0, sum = 0;
    for(int i = 0; i < 26; i++){
        if(bor[v].find(i) == bor[v].end()){
            continue;
        }
        int to = bor[v][i];
        dfs(to);
        sum += cnt[to];
        if(dp[to] > mx1){
            mx2 = mx1;
            mx1 = dp[to];
        }
        else if(dp[to] > mx2){
            mx2 = dp[to];
        }
        dp[v] = max(dp[v], dp[to]);
    }
    if(cnt[v]){
        dp[v] += 1 + max(0, sum - 1);
    }
    else{
        dp[v] = 0;
    }
    ans = max(ans, mx1 + mx2 + cnt[v] + max(0, sum - 2));
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> s;
        reverse(s.begin(), s.end());
        for(auto &it : s){
            it -= 'a';
        }
        Add(s);
    }
    dfs(0);
    cout << ans;
}

• Subtask 1: 126 / 140