oj.uz

Submission #25369

# Submission time Handle Problem Language Result Execution time Memory
25369 2017-06-21T15:19:26 Z samir_droubi Rima (COCI17_rima) C++14
14 / 140
 179 ms 50812 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 43816 KB Output isn't correct
2 Correct 3 ms 43816 KB Output is correct
3 Incorrect 3 ms 43816 KB Output isn't correct
4 Runtime error 179 ms 50812 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 126 ms 43948 KB Output isn't correct
6 Runtime error 26 ms 44636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 26 ms 44624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 44632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 96 ms 44904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 19 ms 44644 KB Execution killed with signal 11 (could be triggered by violating memory limits)