Submission #474457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474457	2021-09-18T09:37:06 Z	Lam_lai_cuoc_doi	Rima (COCI17_rima)	C++17	140 / 140	337 ms	144860 KB

rima

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;

struct node
{
    node *child[26];
    int v, longest;
    bool endhere;
    node()
    {
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;
        v = 0;
        endhere = 0;
        longest = 0;
    }
};

struct trie
{
    node root;

    void Update(const string &s)
    {
        node *a = &root;
        int id(0);

        while (1)
        {
            if (id == (int)s.size())
            {
                a->endhere = 1;
                return;
            }
            if (!(a->child[s[id] - 'a']))
                a->child[s[id] - 'a'] = new node;
            a = a->child[s[id] - 'a'];
            ++id;
        }
    }

    void dfs(node *a)
    {
        vector<int> chain;

        for (int i = 0; i < 26; ++i)
            if (a->child[i])
            {
                dfs(a->child[i]);
                a->v = max(a->v, a->child[i]->v);

                if (a->child[i]->endhere)
                    chain.emplace_back(a->child[i]->longest);
            }

        sort(chain.rbegin(), chain.rend());

        if (chain.size() >= 2)
            a->v = max(a->v, chain[0] + chain[1] + (int)chain.size() + (a->endhere));

        if (!chain.empty())
            a->longest = chain[0] + (int)chain.size();

        a->v = max(a->v, a->longest + (a->endhere));
    }
} f;

int n;

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;

        reverse(s.begin(), s.end());

        f.Update(s);
    }
}

void Solve()
{
    f.dfs(&f.root);
    cout << f.root.v;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

rima.cpp: In function 'void read(T&)':
rima.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	337 ms	144860 KB	Output is correct
5	Correct	17 ms	1612 KB	Output is correct
6	Correct	87 ms	104812 KB	Output is correct
7	Correct	96 ms	104596 KB	Output is correct
8	Correct	87 ms	104408 KB	Output is correct
9	Correct	113 ms	107880 KB	Output is correct
10	Correct	93 ms	104416 KB	Output is correct