Submission #683061

#	Time	Username	Problem	Language	Result	Execution time	Memory
683061		Ahmed57	Savez (COCI15_savez)	C++14	120 / 120	524 ms	44720 KiB

savez

#include <bits/stdc++.h>

using namespace std;
#define int long long


//Hashing
long long a1 = 911382323 , mod1 = 972663749;
long long a2 = 37 , mod2 = 1000000007;
vector<long long> h1(1000001),h2(1000001),p1(1000001),p2(1000001);
void has(string s){
    h1[0] = 0 , h2[0] = 0;
    for(int i = 0;i<s.size();i++){
        h1[i+1] = (h1[i]*a1+((s[i]-'a')+1))%mod1;
        h2[i+1] = (h2[i]*a2+((s[i]-'a')+1))%mod2;
    }
}
long long q1(int l,int r){return(((h1[r]-h1[l-1]*p1[r-l+1])%mod1)+mod1)%mod1;}
long long q2(int l,int r){return(((h2[r]-h2[l-1]*p2[r-l+1])%mod2)+mod2)%mod2;}
signed main(){
    int n;
    cin>>n;
    p1[0] = 1 , p2[0] = 1;
    for(int i = 1;i<=1e6;i++){
        p1[i] = (p1[i-1]*a1)%mod1;
        p2[i] = (p2[i-1]*a2)%mod2;
    }
    map<string,int> dp;
    long long ma = 0;
    for(int i = 0;i<n;i++){
        string s;cin>>s;
        has(s);
        string v;
        long long mi = 0;
        for(int i = 1;i<=s.size();i++){
            v+=s[i-1];
            if(q1(1,i)==q1((s.size()-i)+1,s.size())&&q2(1,i)==q2((s.size()-i)+1,s.size())){
                mi = max(mi,dp[v]);
            }
        }
        dp[s] = mi+1;
        ma = max(ma,dp[s]);
    }
    cout<<ma;
}

Compilation message (stderr)

savez.cpp: In function 'void has(std::string)':
savez.cpp:13:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0;i<s.size();i++){
      |                   ~^~~~~~~~~
savez.cpp: In function 'int main()':
savez.cpp:35:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int i = 1;i<=s.size();i++){
      |                       ~^~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12