oj.uz

Submission #1096868

# Submission time Handle Problem Language Result Execution time Memory
1096868 2024-10-05T10:03:16 Z DucNguyen2007 Rima (COCI17_rima) C++14
140 / 140
 226 ms 137404 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=5e5+5;
const ll inf=2e18;
int n,ans=0;
struct Node
{
    Node *child[26];
    int val,cnt;
    Node()
    {
        for(int i=0;i<26;i++)
        {
            child[i]=NULL;
        }
        val=0;
        cnt=0;
    }
};
Node root;
struct Trie
{
    void add(string s)
    {
        Node *cur=&root;
        for(auto c:s)
        {
            int d=(c-'a');
            if(!(cur->child[d]))
            {
                cur->child[d]=new Node();
            }
            cur=cur->child[d];
        }
        cur->cnt++;
    }
    void dfs(Node *u)
    {
        vector<int> vec;
        for(int i=0;i<26;i++)
        {
            if(u->child[i])
            {
                dfs(u->child[i]);
                if(u->child[i]->cnt)
                {
                    vec.push_back(u->child[i]->val);
                }
            }
        }
        sort(vec.begin(),vec.end(),greater<int>());
        int m=vec.size();
        if(!m)
        {
            u->val=u->cnt;
        }
        else u->val=max(u->val,u->cnt+vec[0]+m-1);
        ans=max(ans,u->val);
        if(m>1)
        {
            ans=max(ans,u->cnt+vec[0]+vec[1]+m-2);
        }
    }
}f;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        reverse(s.begin(),s.end());
        f.add(s);
    }
    f.dfs(&root);
    cout<<ans;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 226 ms 137404 KB Output is correct
5 Correct 14 ms 3944 KB Output is correct
6 Correct 63 ms 90896 KB Output is correct
7 Correct 62 ms 90664 KB Output is correct
8 Correct 63 ms 90440 KB Output is correct
9 Correct 80 ms 96076 KB Output is correct
10 Correct 63 ms 90372 KB Output is correct