Submission #1096868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096868		DucNguyen2007	Rima (COCI17_rima)	C++14	140 / 140	226 ms	137404 KiB

rima

#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 / 140