Submission #1096839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096839		DucNguyen2007	Rima (COCI17_rima)	C++14	14 / 140	227 ms	155008 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,dp[maxN+1];
struct Trie
{
    struct Node
    {
        Node *child[26];
        int val;
        Node()
        {
            for(int i=0;i<26;i++)
            {
                child[i]=NULL;
            }
            val=0;
        }
    };
    Node root;
    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];
        }
    }
    void update(string s,int val)
    {
        Node *cur=&root;
        if(s.length()==1)
        {
            cur->val=max(cur->val,val);
        }
        for(int i=0;i<s.length();i++)
        {
            int d=(s[i]-'a');
            cur=cur->child[d];
            if(i>=s.length()-2)
            {
                cur->val=max(cur->val,val);
            }
        }
    }
    int get(string s)
    {
        Node *cur=&root;
        int ans=0,len=s.length();
        if(len==1)
        {
            ans=max(ans,cur->val);
        }
        for(int i=0;i<len;i++)
        {
            int d=(s[i]-'a');
            cur=cur->child[d];
            if(i>=len-2)
            {
                ans=max(ans,cur->val);
                //cout<<i<<" "<<d<<" "<<cur->val<<'\n';
            }
        }
        return ans;
    }
}f;
string s[maxN+1];
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++)
    {
        cin>>s[i];
        reverse(s[i].begin(),s[i].end());
        f.add(s[i]);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=f.get(s[i])+1;
        f.update(s[i],dp[i]);
        //cout<<i<<" "<<dp[i]<<'\n';
    }
    cout<<*max_element(dp+1,dp+n+1);
}

Compilation message (stderr)

rima.cpp: In member function 'void Trie::update(std::string, int)':
rima.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<s.length();i++)
      |                     ~^~~~~~~~~~~
rima.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             if(i>=s.length()-2)
      |                ~^~~~~~~~~~~~~~

• Subtask 1: 14 / 140