답안 #1096839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1096839	2024-10-05T09:06:03 Z	DucNguyen2007	Rima (COCI17_rima)	C++14	14 / 140	227 ms	155008 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;
        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

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.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	15964 KB	Output isn't correct
4	Incorrect	227 ms	155008 KB	Output isn't correct
5	Incorrect	30 ms	22344 KB	Output isn't correct
6	Incorrect	100 ms	83848 KB	Output isn't correct
7	Incorrect	93 ms	83528 KB	Output isn't correct
8	Incorrect	95 ms	83336 KB	Output isn't correct
9	Incorrect	134 ms	91808 KB	Output isn't correct
10	Incorrect	100 ms	83408 KB	Output isn't correct