oj.uz

Submission #99169

# Submission time Handle Problem Language Result Execution time Memory
99169 2019-03-01T11:58:35 Z dalgerok Rima (COCI17_rima) C++17
126 / 140
 1000 ms 186048 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 141304 KB Output is correct
2 Correct 149 ms 141304 KB Output is correct
3 Correct 138 ms 141300 KB Output is correct
4 Execution timed out 1091 ms 174920 KB Time limit exceeded
5 Correct 181 ms 141688 KB Output is correct
6 Correct 229 ms 185228 KB Output is correct
7 Correct 222 ms 185244 KB Output is correct
8 Correct 233 ms 185140 KB Output is correct
9 Correct 269 ms 186048 KB Output is correct
10 Correct 236 ms 185244 KB Output is correct