oj.uz

Submission #245229

# Submission time Handle Problem Language Result Execution time Memory
245229 2020-07-05T19:36:02 Z VEGAnn Rima (COCI17_rima) C++14
126 / 140
 262 ms 71544 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){
    if (mrk[v]){
        f[v][0] = f[v][1] = f[v][2] = 1;

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

            if (u == 0) continue;

            dfs(u);

            if (mrk[u]) f[v][2]++;

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

            if (mrk[u]) f[v][1]++;

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

            if (mrk[u]) f[v][0]++;
        }

        for (int tp = 0; tp < 3; tp++)
            ans = max(ans, f[v][tp]);
    } else {
        for (int ch = 0; ch < 26; ch++)
            if (nt[v][ch] > 0)
                dfs(nt[v][ch]);
    }
}

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
126.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 424 KB Output is correct
4 Incorrect 262 ms 71544 KB Output isn't correct
5 Correct 24 ms 1784 KB Output is correct
6 Correct 49 ms 46088 KB Output is correct
7 Correct 48 ms 46108 KB Output is correct
8 Correct 46 ms 46040 KB Output is correct
9 Correct 70 ms 48212 KB Output is correct
10 Correct 48 ms 46068 KB Output is correct