Submission #245229

#	Time	Username	Problem	Language	Result	Execution time	Memory
245229		VEGAnn	Rima (COCI17_rima)	C++14	126 / 140	262 ms	71544 KiB

rima

#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 / 140