Submission #631102

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
631102	2022-08-17T17:07:03 Z	inksamurai	Rima (COCI17_rima)	C++17	140 / 140	298 ms	111136 KB

rima

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3phCa4T ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

struct N{
	int nxt[26];
};

signed main(){
_3phCa4T;
	int n;
	cin>>n;

	vec(N) trie;
	trie.pb({});
	vi usd={0};
	rep(i,n){
		string s;
		cin>>s;
		reverse(s.begin(), s.end());
		// print(s);
		int rt=0;
		rep(j,sz(s)){
			int x=s[j]-'a';
			if(!trie[rt].nxt[x]){
				trie[rt].nxt[x]=sz(trie);
				trie.pb({});
				// print(trie[rt].nxt[x]);
				usd.pb(0);
			}
			rt=trie[rt].nxt[x];
		}
		usd[rt]=1;
		// print(rt);
	}

	vi dp(sz(trie));
	int ans=0;
	auto dfs=[&](auto self,int v)->void{
		int cnt=0;
		pii p={0,0};
		rep(x,26){
			int u=trie[v].nxt[x];
			if(u){
				self(self,u);
				if(dp[u]>p.fi){
					p.se=p.fi;
					p.fi=dp[u];
				}else if(dp[u]>p.se){
					p.se=dp[u];
				}
				cnt+=usd[u];
			}
		}
		// print(v,p.fi,p.se,usd[v]);
		ans=max(ans,p.fi+p.se+cnt-min(cnt,2)+usd[v]);
		if(usd[v]){
			dp[v]=1+p.fi+cnt-min(cnt,1);
		}
	};
	dfs(dfs,0);
	print(ans);

}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	388 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	298 ms	111136 KB	Output is correct
5	Correct	20 ms	784 KB	Output is correct
6	Correct	97 ms	55964 KB	Output is correct
7	Correct	82 ms	55932 KB	Output is correct
8	Correct	84 ms	55920 KB	Output is correct
9	Correct	112 ms	56160 KB	Output is correct
10	Correct	78 ms	55988 KB	Output is correct