Submission #485559

#TimeUsernameProblemLanguageResultExecution timeMemory
485559AkiYuuRima (COCI17_rima)C++17
140 / 140
211 ms78036 KiB
#include <bits/stdc++.h> #define task "GROUP" #define ll long long #define ld long double #define pb(u) emplace_back(u) #define ffw(i,a,b) for (ll i = a; i <= b; i++) #define fbw(i,b,a) for (ll i = b; i >= a; i--) #define adj(v,adj,u) for (auto v : adj[u]) #define rep(i,a) for (auto i : a) #define reset(a) memset(a, 0, sizeof(a)) #define sz(a) a.size() #define all(a) a.begin(),a.end() using namespace std; inline namespace FastIO { const int BSZ = 1<<15; char ibuf[BSZ]; int ipos, ilen; char nc() { // if (ipos == ilen) { ipos = 0; ilen = fread(ibuf,1,BSZ,stdin); if (!ilen) return EOF; } return ibuf[ipos++]; } void readstr(string& x) { char ch; while (isspace(ch = nc())); do { x += ch; } while (!isspace(ch = nc()) && ch != EOF); } template<class T> void readnum(T& x){ char ch; int sgn = 1; while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1; x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0'); x *= sgn; } } const int mxn = 1e6 + 5; typedef pair<ll, ll> ii; void fastio(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); } // _oo0oo_ // o8888888o // 88" . "88 // (| -_- |) // 0\ = /0 // ___/`---'\___ // .' \| |// '. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' |_/ | // \ .-\__ '-' ___/-. / // ___'. .' /--.--\ `. .'___ // ."" '< `.___\_<|>_/___.' >' "". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `_. \_ __\ /__ _/ .-` / / // =====`-.____`.___ \_____/___.-`___.-'===== // int trie[3000006][30]; ll cnt = 0; bool IsEnd[3000006]; int n; int res = 0; void add(string s){ int node = 0; for (char c : s){ int x = c - 'a'; if (trie[node][x] == 0 ) trie[node][x] = ++cnt; node = trie[node][x]; } IsEnd[node] = 1; } int dp[3000006]; void dfs(int u){ int v, max1 = 0,max2 = 0,child = 0; ffw(i,'a' - 'a', 'z' - 'a'){ v = trie[u][i]; if ( v == 0 ) continue; dfs(v); if (IsEnd[v]){ child++; if (dp[v] >= max1){ max2 = max1; max1 = dp[v]; } else{ if (dp[v] > max2) max2 = dp[v]; } } } dp[u] = max1 + child; res = max(res, max1 + max2 + child + IsEnd[u]); } void solve(){ int n; cin >> n; ffw(i,1,n) { string s; cin >> s; reverse(all(s)); add(s); } dfs(0); cout << res; } int main(){ fastio(); solve(); }

Compilation message (stderr)

rima.cpp:57:1: warning: multi-line comment [-Wcomment]
   57 | //                 / \|||  :  |||// \
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...