| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 257622 |
2020-08-04T13:40:47 Z |
uacoder123 |
Rima (COCI17_rima) |
C++14 |
|
404 ms |
150256 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int arr[3000001][26];
vi al[3000001];
int val[3000001];
int dp[3000001][2],co=1,ans=0;
void ins(string &s)
{
int cur=0;
for(int i=0;i<s.size();++i)
{
if(arr[cur][s[i]-'a']==0)
{
al[cur].pb(co);
arr[cur][s[i]-'a']=co++;
}
cur=arr[cur][s[i]-'a'];
if(i==s.size()-1)
val[cur]++;
}
}
void dfs(int node)
{
int v=0;
dp[node][0]=val[node];
for(int i=0;i<al[node].size();++i)
{
dfs(al[node][i]);
v+=val[al[node][i]];
}
int max1=-1,max2=-1;
for(int i=0;i<al[node].size();++i)
if(max1==-1||dp[al[node][i]][0]>dp[al[node][max1]][0])
max1=i;
for(int i=0;i<al[node].size();++i)
if(i!=max1&&(max2==-1||dp[al[node][max2]][0]<dp[al[node][i]][0]))
max2=i;
if(max1!=-1)
{
for(int i=0;i<al[node].size();++i)
{
if(val[al[node][i]]==0)
continue;
dp[al[node][i]][1]=dp[al[node][max1]][0]+v-val[al[node][max1]];
if(max2!=-1)
ans=max(ans,dp[al[node][i]][1]+dp[al[node][max2]][0]-val[al[node][max2]]+val[node]);
else
ans=max(ans,dp[al[node][i]][1]+val[node]);
}
}
for(int i=0;i<al[node].size();++i)
if(val[node]!=0)
dp[node][0]=max(dp[node][0],val[node]+dp[al[node][i]][1]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
string s;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>s;
reverse(all(s));
ins(s);
}
dfs(0);
cout<<ans<<endl;
return(0);
}
Compilation message
rima.cpp: In function 'void ins(std::__cxx11::string&)':
rima.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<s.size();++i)
~^~~~~~~~~
rima.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i==s.size()-1)
~^~~~~~~~~~~~
rima.cpp: In function 'void dfs(int)':
rima.cpp:43:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
rima.cpp:49:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
rima.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
rima.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
rima.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
70784 KB |
Output is correct |
| 2 |
Correct |
44 ms |
70904 KB |
Output is correct |
| 3 |
Correct |
44 ms |
70776 KB |
Output is correct |
| 4 |
Correct |
404 ms |
150256 KB |
Output is correct |
| 5 |
Correct |
65 ms |
71676 KB |
Output is correct |
| 6 |
Correct |
106 ms |
128136 KB |
Output is correct |
| 7 |
Correct |
98 ms |
127896 KB |
Output is correct |
| 8 |
Correct |
108 ms |
127912 KB |
Output is correct |
| 9 |
Correct |
132 ms |
129852 KB |
Output is correct |
| 10 |
Correct |
116 ms |
127876 KB |
Output is correct |
