Submission #497206

#	Time	Username	Problem	Language	Result	Execution time	Memory
497206		julian33	Rima (COCI17_rima)	C++14	56 / 140	1061 ms	48400 KiB

rima

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=3e6+5; //make sure this is right
const int mod=1e9+7;
const int mod2=988244353;
const int b=131;

/*
lets denote a string by its identity
{hash of 1->n-1, full hash, len(s)} -> {x,y,l}
all strings with same x can be considered as part of same component
dp[y] = dp[x] + sz(x)
*/

ll h[mxN],h2[mxN];

struct identity{
    pii x,y;
    int l;
    bool operator<(const identity &o) const{
        return l<o.l;
    }
};

map<pii,int> dp,cnt;

int main(){
    cin.sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif

    int n; cin>>n;
    vector<identity> all;
    for(int i=0;i<n;i++){
        string s; cin>>s;
        reverse(s.begin(),s.end());
        identity cur;
        for(int j=1;j<=sz(s);j++){
            h[j]=(h[j-1]*b+s[j-1])%mod;
            h2[j]=(h2[j-1]*b+s[j-1])%mod2;
            if(j+1==sz(s)) cur.x={h[j],h2[j]};
            else if(j==sz(s)) cur.y={h[j],h2[j]};
        }
        cnt[cur.x]++;
        cur.l=sz(s);
        all.pb(cur);
    }
    sort(all.begin(),all.end());
    int ans=0;
    for(auto &[x,y,l]:all){
        if(!dp.count(x)) dp[y]=cnt[x];
        else dp[y]=dp[x]+cnt[x];
        maxa(ans,dp[y]);
    }
    cout<<ans<<"\n";
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:80:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for(auto &[x,y,l]:all){
      |               ^

• Subtask 1: 56 / 140