Submission #257622

#	Time	Username	Problem	Language	Result	Execution time	Memory
257622		uacoder123	Rima (COCI17_rima)	C++14	140 / 140	404 ms	150256 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][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 (stderr)

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)
                   ~^~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140