Submission #696427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
696427	2023-02-06T13:15:49 Z	mousey	Rima (COCI17_rima)	C++14	140 / 140	272 ms	117068 KB

rima

#include <bits/stdc++.h>
//#define int long long
#define vi vector <int>
#define vv vector <vi>
#define pi pair <int, int>
#define vip vector <pi>
#define pb push_back
#define f first
#define s second
#define nl cout<<"\n"
using namespace std;

const int mod=1e9+7;
const double eps=1e-9;
const int N=5e5;
int n;

struct Node{
	int next[26]={};
	bool end=false;
};

struct Trie{
	vector <Node> tree;
	vi dp;
	int cur=1, ans=0;
	
	Trie()
	{
		tree.emplace_back();
		dp.emplace_back();
	}
	
	void add(string s)
	{
		int crr=0;
		for(int j = s.size()-1; j >= 0; j--)
		{
			char i=s[j];
			if(tree[crr].next[i-'a']) crr=tree[crr].next[i-'a'];
			else tree.emplace_back(), dp.emplace_back(), tree[crr].next[i-'a']=cur, crr=cur, cur++;
		}
		tree[crr].end=true;
	}
	
	void dfs(int u)
	{
		int sum=0;
		vi v;
		for(int i = 0; i < 26; i++)
		{
			if(tree[u].next[i])
			{
				dfs(tree[u].next[i]);
				if(tree[tree[u].next[i]].end) 
				{
					v.pb(dp[tree[u].next[i]]);
					dp[u]=max(dp[u], dp[tree[u].next[i]]);
					sum++;
				}
			}
		}
		if(sum>0) dp[u]+=sum-1;
		if(tree[u].end) dp[u]++;
		if(tree[u].end || u==0)
		{
			if(v.size()>1)
			{
				sort(v.begin(), v.end());
				if(u==0) ans=max(ans, v[v.size()-1]+v[v.size()-2]+sum-2);
				else ans=max(ans, v[v.size()-1]+v[v.size()-2]+1+sum-2);
			}
		}
		ans=max(ans, dp[u]);
	}
};

Trie T;

void input()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		T.add(s);
	}
}

void solve()
{
	T.dfs(0);
	cout << T.ans;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
//    freopen("math.inp", "r", stdin);
//    freopen("math.out", "w", stdout);
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        input();
        solve();
        nl;
    }
}

/*
6
a
b
c
d
e
f
*/

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	272 ms	117068 KB	Output is correct
5	Correct	18 ms	3232 KB	Output is correct
6	Correct	76 ms	73672 KB	Output is correct
7	Correct	84 ms	73628 KB	Output is correct
8	Correct	72 ms	73384 KB	Output is correct
9	Correct	93 ms	77476 KB	Output is correct
10	Correct	72 ms	73408 KB	Output is correct