Submission #25369

#	Time	Username	Problem	Language	Result	Execution time	Memory
25369		samir_droubi	Rima (COCI17_rima)	C++14	14 / 140	179 ms	50812 KiB

rima

#include <bits/stdc++.h>
using namespace std;
int n;
const int mxn=(1e5)+5;
int trie[mxn*3][27];
vector<int>dp[mxn*3];
int pr[mxn*3];
int my_node[mxn*5];
string t;
int cur=0;
void add(int id)
{
	int v=0;
	for(int i=t.length()-1;i>=0;--i)
	{
		int e=t[i]-'a';
		if(trie[v][e])v=trie[v][e];
		else
		{
			++cur;
			pr[cur]=v;
			trie[v][e]=cur;
			v=cur;
		}
	}
	dp[v].push_back(1);
	my_node[id]=v;
}
int ans=0;
void pros(int v)
{
	int vl=dp[v].back();
	ans=max(ans,vl);
	if(dp[pr[v]].size())
	{
		dp[pr[v]].back()=max(dp[pr[v]].back(),vl+1);
		for(int i=0;i<26;++i)
		{
			int u=trie[pr[v]][i];
			if(!u)continue;
			if(!dp[u].size())continue;
			dp[u].back()=max(dp[u].back(),vl+1);
		}
	}
	for(int i=0;i<26;++i)
	{
		int u=trie[v][i];
		if(u==v)continue;
		if(!u)continue;
		if(!dp[u].size())continue;
		dp[u].back()=max(dp[u].back(),vl+1);
	}
	dp[v].pop_back();
	if(!dp[v].size())return;
	dp[v].back()=max(dp[v].back(),vl+1);
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		cin>>t;
		add(i);
	}
	for(int i=0;i<n;++i)
	{
		int v=my_node[i];
		pros(v);
	}
	printf("%d\n",ans);
	return 0;	
}

Compilation message (stderr)

rima.cpp: In function 'int main()':
rima.cpp:59:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

• Subtask 1: 14 / 140