Submission #474433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
474433	2021-09-18T08:47:35 Z	Lam_lai_cuoc_doi	Rima (COCI17_rima)	C++17	14 / 140	323 ms	134744 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;
    node()
    {
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;
        v = 0;
    }
};

struct trie
{
    node root;

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

        while (1)
        {
            if (id == (int)s.size())
            {
                a->v = max(a->v, v);
                return;
            }
            if (!(a->child[s[id] - 'a']))
                a->child[s[id] - 'a'] = new node;
            a = a->child[s[id] - 'a'];
            ++id;
        }
    }
    int Get(const string &s)
    {

        int ans(0), id(0);
        node *a = &root;

        while (1)
        {
            if (id >= (int)s.size() - 1)
            {
                if (id != (int)s.size())
                    ans = max(ans, a->v);

                for (int i = 0; i < 26; ++i)
                    if ((id != (int)s.size() - 1 || i != s[id] - 'a') && a->child[i])
                        ans = max(ans, a->child[i]->v);
            }

            if (id == (int)s.size())
                break;

            if (!(a->child[s[id] - 'a']))
                break;
            a = a->child[s[id] - 'a'];
            ++id;
        }

        return ans;
    }
} f;

int n;

void Read()
{
    cin >> n;
}

void Solve()
{
    int ans(0);
    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());

        int x = f.Get(s) + 1;
        ans = max(ans, x);

        f.Update(s, x);
    }

    cout << ans;
}

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

14.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	Output isn't correct
2	Correct	0 ms	332 KB	Output is correct
3	Incorrect	0 ms	332 KB	Output isn't correct
4	Incorrect	323 ms	134744 KB	Output isn't correct
5	Incorrect	22 ms	872 KB	Output isn't correct
6	Incorrect	53 ms	66676 KB	Output isn't correct
7	Incorrect	44 ms	66564 KB	Output isn't correct
8	Incorrect	45 ms	66548 KB	Output isn't correct
9	Incorrect	76 ms	69520 KB	Output isn't correct
10	Incorrect	43 ms	66580 KB	Output isn't correct