Submission #520672

#TimeUsernameProblemLanguageResultExecution timeMemory
520672kakayoshiRima (COCI17_rima)C++14
14 / 140
265 ms110436 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pi; typedef pair<pair<ll, ll>,ll > pii; typedef vector <ll> vi; #define forw(i,a,b) for (ll i=a;i<=(b);i++) #define forb(i,a,b) for (ll i=a;i>=(b);i--) #define fast {ios::sync_with_stdio(false); cin.tie(0); } #define fi first #define se second #define pu push #define puf push_front #define pb push_back #define pof pop_front #define pob pop_back #define fr front #define all(a) a.begin(),a.end() const ll oo=1e18; const ll mod=1337377; const int base=31; const int tx[5]={0,-1,0,1,0}; const int ty[5]={0,0,1,0,-1}; const ll maxN=3e5+5; const ll maxM=1e6+5; const ll block=700; int out, save[maxM][30],dem,n; bool ed[maxM]; vector <int> edge[maxM]; pi largest[maxM]; void update(int &nhat, int &nhi, int val) { if (val>=nhat) { nhi=nhat; nhat=val; } else if (val>=nhi) nhi=val; return; } void dfs(int u) { largest[u]={0,0}; int tmp=0; for(auto v:edge[u]) { tmp+=ed[v]; dfs(v); update(largest[u].fi,largest[u].se,largest[v].fi); } tmp-=(largest[u].fi>0); out=max(out,largest[u].fi+largest[u].se+tmp); if (!ed[u]) largest[u]={0,0}; else largest[u].fi=1+tmp+(largest[u].se>0); return; } void solve() { cin>>n; forw(i,1,n) { string s;cin>>s; int id=0; reverse(all(s)); for(auto c:s) { if (save[id][c-'a']==0) { save[id][c-'a']=++dem; edge[id].pb(dem); } id=save[id][c-'a']; } ed[id]=1; } // build dfs(0); cout<<out; } int main() { fast; //freopen("test.inp","r",stdin); //freopen("test.out","w",stdout); int t=1; //cin>>t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...