답안 #1096837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096837	2024-10-05T08:41:31 Z	DucNguyen2007	Rima (COCI17_rima)	C++14	14 / 140	206 ms	154948 KB

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;
        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();
        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

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

Subtask #1

14.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	6 ms	15964 KB	Output isn't correct
2	Correct	6 ms	15964 KB	Output is correct
3	Incorrect	6 ms	15960 KB	Output isn't correct
4	Incorrect	206 ms	154948 KB	Output isn't correct
5	Incorrect	31 ms	22364 KB	Output isn't correct
6	Incorrect	104 ms	84096 KB	Output isn't correct
7	Incorrect	97 ms	83488 KB	Output isn't correct
8	Incorrect	92 ms	83336 KB	Output isn't correct
9	Incorrect	131 ms	91780 KB	Output isn't correct
10	Incorrect	107 ms	83244 KB	Output isn't correct