oj.uz

Submission #99168

# Submission time Handle Problem Language Result Execution time Memory
99168 2019-03-01T11:58:02 Z dalgerok Rima (COCI17_rima) C++17
126 / 140
 1000 ms 209416 KB 
#include<bits/stdc++.h>
using namespace std;


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




int n, cnt[M], sz, dp[M], ans;
unordered_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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 164756 KB Output is correct
2 Correct 167 ms 164732 KB Output is correct
3 Correct 166 ms 164816 KB Output is correct
4 Execution timed out 1094 ms 200700 KB Time limit exceeded
5 Correct 310 ms 165240 KB Output is correct
6 Correct 395 ms 208808 KB Output is correct
7 Correct 407 ms 208792 KB Output is correct
8 Correct 378 ms 208736 KB Output is correct
9 Correct 476 ms 209416 KB Output is correct
10 Correct 396 ms 208636 KB Output is correct