Submission #1015311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015311		May27_th	Savez (COCI15_savez)	C++17	0 / 120	68 ms	14268 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;
  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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12