oj.uz

Submission #683061

# Submission time Handle Problem Language Result Execution time Memory
683061 2023-01-17T15:31:14 Z Ahmed57 Savez (COCI15_savez) C++14
120 / 120
 524 ms 44720 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);
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

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

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31572 KB Output is correct
2 Correct 27 ms 31580 KB Output is correct
3 Correct 28 ms 31612 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31560 KB Output is correct
2 Correct 29 ms 31572 KB Output is correct
3 Correct 35 ms 31788 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 34696 KB Output is correct
2 Correct 517 ms 34764 KB Output is correct
3 Correct 524 ms 35228 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31628 KB Output is correct
2 Correct 222 ms 37660 KB Output is correct
3 Correct 391 ms 44720 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 32528 KB Output is correct
2 Correct 132 ms 32644 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 32468 KB Output is correct
2 Correct 135 ms 32708 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 32460 KB Output is correct
2 Correct 113 ms 32496 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 32716 KB Output is correct
2 Correct 146 ms 32672 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 32700 KB Output is correct
2 Correct 131 ms 32716 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 32836 KB Output is correct
2 Correct 167 ms 32984 KB Output is correct
3 Correct 238 ms 33520 KB Output is correct