Submission #991890

#TimeUsernameProblemLanguageResultExecution timeMemory
991890LOLOLORima (COCI17_rima)C++14
140 / 140
169 ms67088 KiB
#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 + tail[p]); 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 timeMemoryGrader output
Fetching results...