Submission #475344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
475344	2021-09-22T03:46:36 Z	cpp219	Rima (COCI17_rima)	C++14	56 / 140	702 ms	103736 KB

rima

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
typedef pair<ld,ll> LD;
const ll N = 5e5 + 9;
const ll mod = 982451653;
const ll base = 31;

string s[N];
vector<ll> Hash[N];
ll n,PW[N*6],ans;
unordered_map<ll,ll> val;

bool lf(string a,string b){
    return (a.size() < b.size() || a.size() == b.size() && a < b);
}

ll GetHash(ll id,ll L,ll R){
    return (Hash[id][R] - Hash[id][L - 1]*PW[R - L + 1] + mod*mod)%mod;
}

ll Prefix1(ll id){
    return GetHash(id,1,s[id].size() - 2);
}

ll PrefixAll(ll id){
    return Hash[id][s[id].size() - 1];
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    PW[0] = 1;
    for (ll i = 1;i < N*6;i++) PW[i] = (PW[i - 1] * base)%mod;
    cin>>n;
    for (ll i = 1;i <= n;i++){
        cin>>s[i]; reverse(s[i].begin(),s[i].end());
        s[i] = ' ' + s[i];
    }
    sort(s + 1,s + n + 1,lf);
    for (ll i = 1;i <= n;i++){
        ll sz = s[i].size() - 1; Hash[i].resize(sz + 1);
        for (ll j = 1;j <= sz;j++)
            Hash[i][j] = (Hash[i][j - 1] * base + s[i][j] - 'a' + 1)%mod;
    }

    //for (ll i = 1;i <= n;i++) cout<<s[i]<<"\n"; exit(0);
    //cout<<Prefix1(4)<<" "<<GetHash(4,1,3); return 0;
    for (ll i = 1;i <= n;i){
        //cout<<i<<"\n";
        ll j = i + 1,prv = Prefix1(i);
        while(j <= n && prv == Prefix1(j) && s[j].size() == s[i].size()) j++;
        for (ll l = i;l < j;l++){
            ll now = PrefixAll(l);
            val[now] = max(val[now],j - i + val[prv]);
            ans = max(ans,val[now]);
        }
        //cout<<i<<" "<<j<<"\n";
        i = j; //debug(i);
    }
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

rima.cpp: In function 'bool lf(std::string, std::string)':
rima.cpp:20:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     return (a.size() < b.size() || a.size() == b.size() && a < b);
      |                                    ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
rima.cpp: In function 'int main()':
rima.cpp:58:26: warning: for increment expression has no effect [-Wunused-value]
   58 |     for (ll i = 1;i <= n;i){
      |                          ^
rima.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	51140 KB	Output is correct
2	Correct	39 ms	51180 KB	Output is correct
3	Correct	39 ms	51192 KB	Output is correct
4	Incorrect	702 ms	103736 KB	Output isn't correct
5	Correct	89 ms	76612 KB	Output is correct
6	Incorrect	52 ms	56828 KB	Output isn't correct
7	Incorrect	50 ms	55764 KB	Output isn't correct
8	Incorrect	46 ms	55080 KB	Output isn't correct
9	Incorrect	115 ms	78848 KB	Output isn't correct
10	Incorrect	47 ms	55204 KB	Output isn't correct