# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
701339 | fdnfksd | Rima (COCI17_rima) | C++14 | 212 ms | 151828 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=int;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct TrieNode
{
ll val;
TrieNode* child[26];
TrieNode()
{
val=0;
for(int i=0;i<26;i++) child[i]=nullptr;
}
};
TrieNode *root=new TrieNode();
void add(string s,ll val)
{
auto p=root;
ll n=s.size()-1;
for(int i=1;i<n;i++)
{
if(p->child[s[i]-'a']==nullptr)
{
p->child[s[i]-'a']=new TrieNode();
}
p=p->child[s[i]-'a'];
}
p->val=max(p->val,val);
for(int i=n;i<=n;i++)
{
if(p->child[s[i]-'a']==nullptr)
{
p->child[s[i]-'a']=new TrieNode();
}
p=p->child[s[i]-'a'];
}
p->val=max(p->val,val);
}
ll get(string s)
{
auto p=root;
ll ans=0;
ll n=s.size()-1;
for(int i=1;i<n;i++)
{
if(p->child[s[i]-'a']==nullptr)
{
p->child[s[i]-'a']=new TrieNode();
}
p=p->child[s[i]-'a'];
}
ans=max(ans,p->val);
for(int i=n;i<=n;i++)
{
if(p->child[s[i]-'a']==nullptr)
{
p->child[s[i]-'a']=new TrieNode();
}
p=p->child[s[i]-'a'];
}
ans=max(ans,p->val);
return ans;
}
ll n;
string s[maxN];
void solve()
{
cin >> n;
ll ans=0;
for(int i=1;i<=n;i++)
{
cin >> s[i];
reverse(s[i].begin(),s[i].end());
s[i]=' '+s[i];
ll x=get(s[i])+1;
ans=max(ans,x);
add(s[i],x);
}
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |