#include <bits/stdc++.h>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
class Trie {
private:
int n;
vi cnt, dp;
vvi trie;
public:
Trie(): n(0), cnt(1), trie(1, vi(26, -1)) {};
void append(const string &s) {
int x = 0, y;
for (const char &c : s) {
y = c - 'a';
if (trie[x][y] < 0) {
trie[x][y] = ++n;
trie.pb(vi(26, -1));
cnt.pb(0);
}
x = trie[x][y];
}
++cnt[x];
}
int DP(int x) {
if (dp[x] < 0) {
dp[x] = 0;
fore(y, 0, 26)
if (trie[x][y] >= 0 && cnt[trie[x][y]] > 0)
maxi(dp[x], DP(trie[x][y]));
fore(y, 0, 26)
if (trie[x][y] >= 0)
dp[x] += cnt[trie[x][y]];
}
return dp[x];
}
int solve() {
dp.resize(n + 1, -1);
return DP(0);
}
};
const int maxN = 5e5 + 5;
int n;
string word[maxN];
Trie trie;
void input() {
cin >> n;
fore(i, 0, n) {
cin >> word[i];
reverse(all(word[i]));
}
}
void subtask1() {
const int base = 2003, MOD = 1e9 + 9999, N = n + 5;
int res = 0, length = 0, power[N];
vvi lcp(N, vi(N)), dp(1 << n, vi(n));
vector<vector<bool> > seen(1 << n, vector<bool>(n, false));
vi h[N];
const function<int(vi, int, int)> query = [&](const vi &h, const int l, const int r) -> int {
return (h[r] - 1LL * h[l - 1] * power[r - l + 1] % MOD + MOD) % MOD;
};
const function<int(int, int)> findLCP = [&](int x, int y) -> int {
const int a = word[x].size(), b = word[y].size();
int lo = 0, hi = min(a, b) + 1, mid;
while (lo + 1 < hi) {
mid = lo + hi >> 1;
if (query(h[x], 1, mid) == query(h[y], 1, mid))
lo = mid;
else
hi = mid;
}
return lo;
};
const function<bool(int, int)> checkConnected = [&](const int a, const int b) -> bool {
return lcp[a][b] >= max(sz(word[a]), sz(word[b])) - 1;
};
const function<int(int, int)> DP = [&](const int mask, const int x) -> int {
if (!seen[mask][x]) {
seen[mask][x] = true;
dp[mask][x] = 1;
fore(y, 0, n)
if (!(mask & (1 << y)) && checkConnected(x, y))
maxi(dp[mask][x], 1 + DP(mask | (1 << y), y));
}
return dp[mask][x];
};
power[0] = 1;
fore(i, 0, n) {
maxi(length, word[i].size());
h[i].pb(0);
for (const char &c : word[i])
h[i].pb((1LL * h[i].back() * base % MOD + c) % MOD);
}
fort(i, 1, length)
power[i] = 1LL * power[i - 1] * base % MOD;
fore(x, 0, n)
fore(y, 0, n)
lcp[x][y] = findLCP(x, y);
// fore(x, 0, n)
// fore(y, 0, n)
// cerr << x << ' ' << y << ' ' << lcp[x][y] << '\n';
fore(x, 0, n)
maxi(res, DP(1 << x, x));
cout << res << '\n';
}
void subtask2() {
fore(i, 0, n)
trie.append(word[i]);
cout << trie.solve() << '\n';
}
int main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
input();
// if (n <= 18)
// subtask1();
// else
subtask2();
return 0;
}
Compilation message
rima.cpp: In lambda function:
rima.cpp:94:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | mid = lo + hi >> 1;
| ~~~^~~~
rima.cpp: In instantiation of 'bool maxi(A&, const B&) [with A = int; B = long unsigned int]':
rima.cpp:117:36: required from here
rima.cpp:15:67: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
15 | template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15956 KB |
Output isn't correct |
| 2 |
Incorrect |
9 ms |
15956 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
15976 KB |
Output isn't correct |
| 4 |
Incorrect |
329 ms |
105076 KB |
Output isn't correct |
| 5 |
Correct |
30 ms |
22084 KB |
Output is correct |
| 6 |
Incorrect |
47 ms |
59856 KB |
Output isn't correct |
| 7 |
Incorrect |
47 ms |
59652 KB |
Output isn't correct |
| 8 |
Incorrect |
55 ms |
59328 KB |
Output isn't correct |
| 9 |
Incorrect |
70 ms |
66664 KB |
Output isn't correct |
| 10 |
Incorrect |
46 ms |
59344 KB |
Output isn't correct |
