# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
991887 | LOLOLO | Rima (COCI17_rima) | C++17 | 166 ms | 69812 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
int cc = 1, root = 0;
int nxt[3000006][26], tail[3000006];
string s;
void add(int &p, int i) {
if (p == 0) {
p = cc;
cc++;
}
if (i == len(s)) {
tail[p] = 1;
return;
}
add(nxt[p][s[i] - 'a'], i + 1);
}
int ans = 0;
int dfs(int p) {
int m1 = 0, m2 = 0, cnt = 0;
for (int i = 0; i < 26; i++) {
if (nxt[p][i]) {
int val = dfs(nxt[p][i]);
if (tail[nxt[p][i]] == 0)
continue;
cnt += 1;
if (m1 < val) {
m2 = m1;
m1 = val;
} else {
m2 = max(m2, val);
}
}
}
ans = max(ans, m1 + m2 + cnt);
return m1 + cnt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s;
reverse(all(s));
add(root, 0);
}
dfs(root);
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |