Submission #1104448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104448		qrn	Savez (COCI15_savez)	C++14	84 / 120	50 ms	9808 KiB

savez

#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 (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++) {
        dp[i] = 1;
        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 (stderr)

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 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