Submission #99170

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
99170	2019-03-01T11:59:24 Z	dalgerok	Rima (COCI17_rima)	C++17	140 / 140	586 ms	67868 KB

rima

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


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




int n, cnt[M], sz, dp[M], ans;
int bor[26][M];
string s;


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

void dfs(int v){
    int mx1 = 0, mx2 = 0, sum = 0;
    for(int i = 0; i < 26; i++){
        int to = bor[i][v];
        if(!to){
            continue;
        }
        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;
    }
    ///cout << v << " " << dp[v] << " " << cnt[v] << "\n";
    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;
}

Compilation message

rima.cpp: In function 'void Add(std::__cxx11::string&)':
rima.cpp:18:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(!bor[it][v]){
                   ^
rima.cpp:19:19: warning: array subscript has type 'char' [-Wchar-subscripts]
             bor[it][v] = ++sz;
                   ^
rima.cpp:21:19: warning: array subscript has type 'char' [-Wchar-subscripts]
         v = bor[it][v];
                   ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	640 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	2 ms	640 KB	Output is correct
4	Correct	586 ms	67868 KB	Output is correct
5	Correct	18 ms	768 KB	Output is correct
6	Correct	122 ms	56452 KB	Output is correct
7	Correct	110 ms	56340 KB	Output is correct
8	Correct	124 ms	56540 KB	Output is correct
9	Correct	167 ms	57768 KB	Output is correct
10	Correct	103 ms	56288 KB	Output is correct