oj.uz

Submission #1104446

# Submission time Handle Problem Language Result Execution time Memory
1104446 2024-10-23T19:14:58 Z qrn Savez (COCI15_savez) C++14
36 / 120
 49 ms 9808 KB 
#include <bits/stdc++.h>
using namespace std;
 
template<class ISqr, class T>
ISqr& operator>>(ISqr& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
 
#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);
 
template <typename T>
void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << endl;
}

 
#define pb push_back
#define ins insert
#define fi first
#define se second
 
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define int long long
#define _ << " " <<
#define no cout << "No" << endl;
#define yes cout << "Yes" << endl;
#define impos cout << -1 << endl;
 
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
 
const int sz = 2e5 + 31;
const int base = 31;
const int mod = 1e18 + 3;

int mult(int a, int b) {
    return (__int128(a) * b) % mod;
}

int add(int a, int b) {
    return a + b >= mod ? (a + b - mod) : a + b; 
}

map<int,int>idx;
int pw[sz];
void solve() {
    pw[0] = 1;
    for(int i = 1; i < sz; i++) {
        pw[i] = mult(pw[i-1], base);
    }
    int n; cin >> n;
    vi dp(n + 1, 0);
    dp[1] = 1;
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        reverse(ALL(s));
        string revs = s;
        reverse(ALL(s));
        int hashpre = 0, hashsuf = 0;
        for(int j = 0; j < sz(s); j++) {
            hashsuf = (hashsuf + mult((revs[j] - 'a' + 1), base)) % mod;
            hashpre = (hashpre + mult((s[j] - 'a' + 1), base)) % mod;
            // cout << hashsuf << " " << hashpre << endl;
            if(hashpre == hashsuf) {
                auto it = idx.find(hashpre);
                if(it == idx.end()) continue;
                dp[i] = max(dp[i], dp[it->se] + 1);
                // cout << dp[i] << " " << dp[it->se] << endl;
            }
        }
        idx[hashpre] = i; // s-in hash valuesini at
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;
}
 
signed main(){
    SPEED;
    int t = 1;
    // cin >> t;
    for(int cs = 1; cs <= t; cs++) {
        solve();
    }
}

Compilation message

savez.cpp: In function 'void solve()':
savez.cpp:68:26: 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]
   68 |         for(int j = 0; j < sz(s); j++) {
      |                          ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Incorrect 3 ms 1872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1872 KB Output is correct
2 Incorrect 11 ms 1872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2300 KB Output is correct
2 Correct 16 ms 2128 KB Output is correct

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3664 KB Output is correct
2 Correct 22 ms 3664 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5104 KB Output is correct
2 Correct 29 ms 5200 KB Output is correct
3 Correct 49 ms 9808 KB Output is correct