oj.uz

Submission #497206

# Submission time Handle Problem Language Result Execution time Memory
497206 2021-12-22T17:37:03 Z julian33 Rima (COCI17_rima) C++14
56 / 140
 1000 ms 48400 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Execution timed out 1061 ms 48400 KB Time limit exceeded
5 Correct 34 ms 3520 KB Output is correct
6 Incorrect 13 ms 6044 KB Output isn't correct
7 Incorrect 12 ms 5880 KB Output isn't correct
8 Incorrect 12 ms 5796 KB Output isn't correct
9 Incorrect 48 ms 9412 KB Output isn't correct
10 Incorrect 9 ms 5840 KB Output isn't correct