Submission #257554

#	Time	Username	Problem	Language	Result	Execution time	Memory
257554		uacoder123	Rima (COCI17_rima)	C++14	56 / 140	430 ms	152412 KiB

rima

#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][i]];
      if(max2!=-1)
        ans=max(ans,dp[al[node][i]][0]+dp[al[node][max2]][0]-val[al[node][max2]]);
      else
        ans=max(ans,dp[al[node][i]][0]);
    }
  }
  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 (stderr)

rima.cpp: In function 'void ins(std::__cxx11::string&)':
rima.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.size();++i)
               ~^~~~~~~~~
rima.cpp:35:9: 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:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
rima.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
rima.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
rima.cpp:57:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<al[node].size();++i)
                 ~^~~~~~~~~~~~~~~~
rima.cpp:68:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~

• Subtask 1: 56 / 140