oj.uz

Submission #245239

# Submission time Handle Problem Language Result Execution time Memory
245239 2020-07-05T19:44:16 Z VEGAnn Rima (COCI17_rima) C++14
140 / 140
 269 ms 70520 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
const int M = 3000100;
string s;
int ed = 1, nt[M][26], n, f[M][3], ans = 1;
bool mrk[M];

void dfs(int v){
    f[v][0] = f[v][1] = f[v][2] = mrk[v];

    for (int ch = 0; ch < 26; ch++){
        int u = nt[v][ch];

        if (u == 0) continue;

        dfs(u);

        if (!mrk[u]) continue;

        f[v][2]++;

        f[v][2] = max(f[v][2], f[v][1] + f[u][1]);

        f[v][1]++;

        f[v][1] = max(f[v][1], f[v][0] + f[u][1]);

        f[v][0]++;
    }

    for (int tp = 0; tp < 3; tp++)
        ans = max(ans, f[v][tp]);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAl

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s;
        reverse(all(s));

        int cur = 1;

        for (int j = 0; j < sz(s); j++){
            int ch = s[j] - 'a';

            if (nt[cur][ch] == 0)
                nt[cur][ch] = ++ed;

            cur = nt[cur][ch];
        }

        mrk[cur] = 1;
    }

    dfs(1);

    cout << ans;

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 269 ms 70520 KB Output is correct
5 Correct 26 ms 768 KB Output is correct
6 Correct 51 ms 49164 KB Output is correct
7 Correct 51 ms 49172 KB Output is correct
8 Correct 49 ms 49112 KB Output is correct
9 Correct 69 ms 50644 KB Output is correct
10 Correct 52 ms 49148 KB Output is correct