Submission #701246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
701246	2023-02-20T16:14:03 Z	tamthegod	Rima (COCI17_rima)	C++17	56 / 140	269 ms	262144 KB

rima

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

#define int long long
#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 = 1e6 + 5;
const int mod = (int)1e14 + 7;
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;
            }
            if(cnt == s.size()) tree[id].val++;
            id = tree[id].child[w];
        }
        tree[id].mark++;
    }
    void dfs(int u)
    {
        for(int i=0; i<30; i++)
        {
            if(tree[u].child[i] == -1) continue;
            int v = tree[u].child[i];
            dfs(v);
            f[u] += f[v];
        }
        if(tree[u].mark) f[u] += tree[u].mark;
        else f[u] = 0;
        res = max(res, f[u]);
    }
};
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();
}
// 1 1 2 3 4 5 1 1 2 6 2 3 4 7 5 1 1 1
// 1 1 2 3 4 5 1 6 7 8 2 3 4 9 5 1 1 1

Compilation message

rima.cpp: In member function 'void Trie::add(std::string)':
rima.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(cnt == s.size()) tree[id].val++;
      |                ~~~~^~~~~~~~~~~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	31828 KB	Output is correct
2	Correct	17 ms	31828 KB	Output is correct
3	Correct	18 ms	31784 KB	Output is correct
4	Runtime error	269 ms	262144 KB	Execution killed with signal 9
5	Correct	31 ms	35776 KB	Output is correct
6	Incorrect	146 ms	167940 KB	Output isn't correct
7	Incorrect	138 ms	167924 KB	Output isn't correct
8	Incorrect	142 ms	167832 KB	Output isn't correct
9	Incorrect	168 ms	170572 KB	Output isn't correct
10	Incorrect	143 ms	167796 KB	Output isn't correct