oj.uz

Submission #1015320

# Submission time Handle Problem Language Result Execution time Memory
1015320 2024-07-06T08:42:22 Z May27_th Savez (COCI15_savez) C++17
120 / 120
 74 ms 33692 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1372 KB Output is correct
2 Correct 16 ms 1588 KB Output is correct
3 Correct 26 ms 2412 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 27 ms 1608 KB Output is correct
3 Correct 33 ms 1692 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1628 KB Output is correct
2 Correct 23 ms 2652 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2392 KB Output is correct
2 Correct 24 ms 3372 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3164 KB Output is correct
2 Correct 23 ms 3932 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3676 KB Output is correct
2 Correct 28 ms 4828 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 7772 KB Output is correct
2 Correct 34 ms 9052 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 12888 KB Output is correct
2 Correct 37 ms 14312 KB Output is correct
3 Correct 74 ms 33692 KB Output is correct