Submission #1015320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015320		May27_th	Savez (COCI15_savez)	C++17	120 / 120	74 ms	33692 KiB

savez

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define i128 __int128
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e6 + 50;
const int INF = 1e9;
const int64_t MOD = (1LL << 61) - 1;
const int64_t BASE = uniform_int_distribution<int64_t>(0, MOD - 1)(rng);
 
__int128 mul(int64_t a, int64_t b) { return (__int128)a * b; }
int64_t mod_mul(int64_t a, int64_t b) { return mul(a, b) % MOD; }
 
int64_t Hash[MAXN], Pow[MAXN];
int64_t calc(int64_t l, int64_t r) { return (Hash[r] - mod_mul(Hash[l], Pow[r - l]) + MOD) % MOD; }
void Solve(void) {
  int N; cin >> N;
  vector<string> words(N);
  map<i64, int> f;
  int mx = 0;
  for (int i = 0; i < N; i ++) {
    cin >> words[i];
    mx = max(mx, (int)words[i].size());
  }
  Pow[0] = 1;
  for (int i = 1; i <= mx; i ++) {
    Pow[i] = mod_mul(Pow[i - 1], BASE);
  }
  // sort(all(words)); words.erase(unique(all(words)), words.end());
  int ans = 0;
  for (auto word : words) {
    Hash[0] = 0;
    int sz = word.size();
    for (int i = 1; i <= sz; i ++) {
      Hash[i] = (mod_mul(Hash[i - 1], BASE) + word[i - 1] - '0' + 1) % MOD;
    }
    int tot = 1;
    for (int i = 1; i <= sz; i ++) {
      if (f.count(Hash[i])) {
        if (Hash[i] == calc(sz - i, sz)) {
          tot = max(tot, f[Hash[i]] + 1);
        }
      }
    }
    f[Hash[sz]] = max(f[Hash[sz]], tot);
    // cout << word << " " << f[Hash[sz]] << "\n";
    ans = max(ans, f[Hash[sz]]);
  }
  cout << ans << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests;
  while (Tests --) {
    Solve();
  }
}

• 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