oj.uz

Submission #229672

# Submission time Handle Problem Language Result Execution time Memory
229672 2020-05-05T19:57:24 Z MohamedAhmed04 Rima (COCI17_rima) C++14
70 / 140
 337 ms 262148 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 3e6 + 10 ;

string arr[MAX] ;
int n ;
int tree[MAX][27] , Cnt[MAX*27] , dp[MAX] , dp2[MAX] , finished[MAX*27] ;

int last = 0 ;

void Insert(string s)
{
	int node = 0 ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		if(i == s.size()-1)
			Cnt[node]++ ;
		char c = s[i] ;
		int idx = c - 'a' ;
		if(!tree[node][idx])
			tree[node][idx] = ++last ;
		node = tree[node][idx] ;
	}
	finished[node] = 1 ;
}

int ans = 0 ;

void solve(int node, string s)
{
	pair<int , int>p = {0 , 0} ;
	pair<int , int>p2 ;
	for(int i = 0 ; i < 26 ; ++i)
	{
		if(!tree[node][i])
			continue ;
		int child = tree[node][i] ;
		s.push_back(i+'a') ;
		solve(child, s) ;
		s.pop_back() ;
		p2 = {max(p.first, dp[child]), min(p.first, dp[child])} ;
		p = max(p , p2) ;
	}
	ans = max(ans , p.first+p.second+Cnt[node]+finished[node]) ;
	dp[node] = p.first + Cnt[node] ;
	if(!finished[node])
		dp[node] = 0 ;
	return ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
	{
		cin>>arr[i] ;
		reverse(arr[i].begin() , arr[i].end()) ;
		Insert(arr[i]) ;
	}
	solve(0, "") ;
	return cout<<ans<<"\n" , 0 ;
}

Compilation message

rima.cpp: In function 'void Insert(std::__cxx11::string)':
rima.cpp:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < s.size() ; ++i)
                  ~~^~~~~~~~~~
rima.cpp:18:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i == s.size()-1)
      ~~^~~~~~~~~~~~~

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94332 KB Output is correct
2 Correct 56 ms 94380 KB Output is correct
3 Correct 56 ms 94328 KB Output is correct
4 Correct 337 ms 169084 KB Output is correct
5 Correct 83 ms 106488 KB Output is correct
6 Runtime error 147 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 143 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 148 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 172 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 145 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)