Submission #739155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
739155	2023-05-10T04:37:53 Z	GrindMachine	Rima (COCI17_rima)	C++17	140 / 140	309 ms	127948 KB

rima

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

struct Trie {
    struct node {
        int f[26];
        int cnt;

        node() {
            memset(f, -1, sizeof f);
            cnt = 0;
        }
    };

    vector<node> tr;
    int siz = 0;

    Trie() {
        tr.pb(node());
        siz++;
    }

    void insert(string s) {
        int u = 0;

        trav(ch, s) {
            int x = ch - 'a';
            if (tr[u].f[x] == -1) {
                tr.pb(node());
                tr[u].f[x] = siz++;
            }

            u = tr[u].f[x];
        }

        tr[u].cnt++;
    }

    vector<int> down;
    string curr = "";

    void dfs(int u) {
        int good = 0;
        int mx = 0;

        rep(ch, 26) {
            int v = tr[u].f[ch];
            if (v == -1) conts;

            curr.pb(char('a' + ch));
            dfs(v);
            curr.pop_back();

            good += tr[v].cnt;
            amax(mx, down[v]);
        }

        if (!tr[u].cnt) {
            down[u] = 0;
        }
        else {
            down[u] = good - 1 + mx;
            amax(down[u], 0);
            down[u]++;
        }

        // debug(curr);
        // debug(down[u]);
    }

    void dfs() {
        down = vector<int>(siz);
        dfs(0);
    }

    int get_ans() {
        int ans = 0;

        rep(u, siz) {
            amax(ans, down[u]);

            vector<int> vals;
            int good = 0;

            rep(ch, 26) {
                int v = tr[u].f[ch];
                if (v != -1) {
                    vals.pb(down[v]);
                    good += tr[v].cnt;
                }
            }

            sort(rall(vals));

            if (sz(vals) >= 2) {
                int val = vals[0] + vals[1] + good - 2 + tr[u].cnt;
                amax(ans, val);
            }
        }

        return ans;
    }
};

void solve(int test_case)
{
    int n; cin >> n;
    vector<string> a(n);
    rep(i, n) cin >> a[i];

    Trie trie;
    rep(i, n) {
        reverse(all(a[i]));
        trie.insert(a[i]);
    }

    trie.dfs();

    int ans = trie.get_ans();
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	309 ms	127948 KB	Output is correct
5	Correct	21 ms	5076 KB	Output is correct
6	Correct	93 ms	68516 KB	Output is correct
7	Correct	89 ms	68112 KB	Output is correct
8	Correct	91 ms	67944 KB	Output is correct
9	Correct	112 ms	73484 KB	Output is correct
10	Correct	89 ms	68008 KB	Output is correct