Submission #701259

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
701259	2023-02-20T16:43:47 Z	tamthegod	Rima (COCI17_rima)	C++17	140 / 140	317 ms	229788 KB

rima

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 3e6 + 5;

const ll oo = 1e18;
int n;
string s[maxN];
int f[maxN];
int res = 0;
void ReadInput()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> s[i];
        reverse(s[i].begin(), s[i].end());
    }
}
struct Trie
{
    struct TNode
    {
        int id;
        int val;
        int mark;
        int child[30];
    };
    vector<TNode> tree;
    void new_node()
    {
        TNode tmp;
        tmp.id = tree.size();
        tmp.val = 0;
        tmp.mark = 0;
        for(int i=0; i<30; i++)
            tmp.child[i] = -1;
        tree.pb(tmp);
    }
    void add(string s)
    {
        int id = 0;
        int cnt = 0;
        for(char c : s)
        {
            cnt++;
            int w = c - 'a';
            if(tree[id].child[w] == -1)
            {
                new_node();
                tree[id].child[w] = tree.size() - 1;
            }
            id = tree[id].child[w];
        }
        tree[id].mark++;
    }
    void dfs(int u)
    {
        vector<int> vc;
        for(int i=0; i<30; i++)
        {
            if(tree[u].child[i] == -1) continue;
            int v = tree[u].child[i];
            dfs(v);
            if(f[v]) vc.pb(f[v]);
            f[u] = max(f[u], f[v]);
        }
        if(vc.empty())
        {
            f[u] = tree[u].mark;
            res = max(res, f[u]);
            return;
        }
        sort(vc.begin(), vc.end(), greater<int>());
        if(vc.size() > 1) res = max(res, vc[0] + vc[1] + tree[u].mark + (int)vc.size() - 2);
        f[u] += vc.size();
        if(tree[u].mark) res = max(res, f[u]);
        else f[u] = 0;
    }
};
void Solve()
{
    Trie tree;
    tree.new_node();
    for(int i=1; i<=n; i++)
        tree.add(s[i]);
    tree.dfs(0);
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    // freopen("sol.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	94364 KB	Output is correct
2	Correct	42 ms	94272 KB	Output is correct
3	Correct	43 ms	94348 KB	Output is correct
4	Correct	317 ms	229788 KB	Output is correct
5	Correct	61 ms	97860 KB	Output is correct
6	Correct	124 ms	163628 KB	Output is correct
7	Correct	146 ms	163468 KB	Output is correct
8	Correct	146 ms	163044 KB	Output is correct
9	Correct	150 ms	167984 KB	Output is correct
10	Correct	119 ms	163340 KB	Output is correct