oj.uz

Submission #1015311

# Submission time Handle Problem Language Result Execution time Memory
1015311 2024-07-06T08:37:10 Z May27_th Savez (COCI15_savez) C++17
0 / 120
 68 ms 14268 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;
  map<string, int> cnt;
  int mx = 0;
  for (int i = 0; i < N; i ++) {
    cin >> words[i];
    cnt[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;
    }
    f[Hash[sz]] = cnt[word];
    for (int i = 1; i < sz; i ++) {
      if (f.count(Hash[i])) {
        if (Hash[i] == calc(sz - i, sz)) {
          f[Hash[sz]] = max(f[Hash[sz]], f[Hash[i]] + cnt[word]);
        }
      }
    }
    // 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
0 / 12.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 12.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 12.0

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

Subtask #7
0 / 12.0

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

Subtask #8
0 / 12.0

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

Subtask #9
0 / 12.0

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

Subtask #10
0 / 12.0

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