// Make the best become better
// No room for laziness
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const ll oo = 1e18;
int n;
string s[maxN];
int f[maxN];
int res = 0;
void ReadInput()
{
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> s[i];
reverse(s[i].begin(), s[i].end());
}
}
struct Trie
{
struct TNode
{
int id;
int val;
int mark;
int child[30];
};
vector<TNode> tree;
void new_node()
{
TNode tmp;
tmp.id = tree.size();
tmp.val = 0;
tmp.mark = 0;
for(int i=0; i<30; i++)
tmp.child[i] = -1;
tree.pb(tmp);
}
void add(string s)
{
int id = 0;
int cnt = 0;
for(char c : s)
{
cnt++;
int w = c - 'a';
if(tree[id].child[w] == -1)
{
new_node();
tree[id].child[w] = tree.size() - 1;
}
if(cnt == s.size()) tree[id].val++;
id = tree[id].child[w];
}
tree[id].mark++;
}
void dfs(int u)
{
vector<int> vc;
for(int i=0; i<30; i++)
{
if(tree[u].child[i] == -1) continue;
int v = tree[u].child[i];
dfs(v);
vc.pb(f[v]);
f[u] = max(f[u], f[v]);
}
if(vc.empty())
{
f[u] = tree[u].mark;
res = max(res, f[u]);
return;
}
if(tree[u].mark)
{
sort(vc.begin(), vc.end(), greater<int>());
if(vc.size() > 1) res = max(res, vc[0] + vc[1] + tree[u].mark);
f[u] += vc[0];
res = max(res, f[u]);
}
else f[u] = 0;
}
};
void Solve()
{
Trie tree;
tree.new_node();
for(int i=1; i<=n; i++)
tree.add(s[i]);
tree.dfs(0);
cout << res;
}
int32_t main()
{
//freopen("sol.inp", "r", stdin);
// freopen("sol.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
Compilation message
rima.cpp: In member function 'void Trie::add(std::string)':
rima.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | if(cnt == s.size()) tree[id].val++;
| ~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
31828 KB |
Output isn't correct |
| 2 |
Incorrect |
15 ms |
31776 KB |
Output isn't correct |
| 3 |
Incorrect |
16 ms |
31828 KB |
Output isn't correct |
| 4 |
Runtime error |
286 ms |
262144 KB |
Execution killed with signal 9 |
| 5 |
Incorrect |
31 ms |
35776 KB |
Output isn't correct |
| 6 |
Incorrect |
145 ms |
167940 KB |
Output isn't correct |
| 7 |
Incorrect |
158 ms |
168000 KB |
Output isn't correct |
| 8 |
Incorrect |
164 ms |
167876 KB |
Output isn't correct |
| 9 |
Incorrect |
166 ms |
170520 KB |
Output isn't correct |
| 10 |
Incorrect |
146 ms |
167760 KB |
Output isn't correct |
