Submission #520663

#TimeUsernameProblemLanguageResultExecution timeMemory
520663HaYoungJoonRima (COCI17_rima)C++17
56 / 140
265 ms161636 KiB
#include <bits/stdc++.h> using namespace std; const int maxsize = 3*1e5; int trie[3000001][26], timer = 0; int dp[3000001], n, res = 0; string a[500001]; vector<int> adj[3000001]; void addString(string s) { int cur = 0; for (char c: s) { int val = c - 'a'; if (!trie[cur][val]) { adj[cur].emplace_back(++timer); trie[cur][val] = timer; } cur = trie[cur][val]; } dp[cur] = 1; } void DFS(int u) { int maxnhanh = 0; for (int v: adj[u]) { DFS(v); maxnhanh = max(maxnhanh,dp[v]); } res = max(dp[u],res); if (dp[u] && maxnhanh) { for (int v: adj[u]) dp[u] += (dp[v] > 0); dp[u] += maxnhanh - 1; res = max(dp[u],res); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; reverse(a[i].begin(),a[i].end()); } for (int i = 1; i <= n; i++) addString(a[i]); DFS(0); cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...