oj.uz

Submission #683056

# Submission time Handle Problem Language Result Execution time Memory
683056 2023-01-17T15:28:37 Z Ahmed57 Savez (COCI15_savez) C++14
0 / 120
 67 ms 64008 KB 
#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);
long long 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

savez.cpp: In function 'long long int 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:17:1: warning: no return statement in function returning non-void [-Wreturn-type]
   17 | }
      | ^
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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 63888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 63804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 64008 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 63948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 63912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 63912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 63868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 67 ms 63888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 63880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 56 ms 63948 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -