Submission #245239

#	Time	Username	Problem	Language	Result	Execution time	Memory
245239		VEGAnn	Rima (COCI17_rima)	C++14	140 / 140	269 ms	70520 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){
    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 / 140