oj.uz

Submission #228055

# Submission time Handle Problem Language Result Execution time Memory
228055 2020-04-29T18:04:07 Z MohamedAhmed04 Rima (COCI17_rima) C++14
56 / 140
 344 ms 161528 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] ;

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] ;
	}
}

int query(string s)
{
	int node = 0 , cnt = Cnt[0] ;
	for(int i = 0 ; i < s.size() ; ++i)
	{
		char c = s[i] ; 
		int idx = c - 'a' ;
		if(!tree[node][idx])
			return 0 ;
		node = tree[node][idx] ;
		if(!Cnt[node] && i != s.size()-1)
			cnt = 0 ;
		else
			cnt += Cnt[node] ;
	}
	return cnt ;
}

bool cmp(string &a , string &b)
{
	if(a.size() == b.size())
		return a < b ;
	else
		return a.size() < b.size() ;
}

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()) ;
	}
	sort(arr , arr + n , cmp) ;
	int ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		string s = arr[i].substr(0 , arr[i].size()-1) ;
		ans = max(ans , query(s)+1) ;
		Insert(arr[i]) ;
	}
	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)
      ~~^~~~~~~~~~~~~
rima.cpp: In function 'int query(std::__cxx11::string)':
rima.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < s.size() ; ++i)
                  ~~^~~~~~~~~~
rima.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(!Cnt[node] && i != s.size()-1)
                    ~~^~~~~~~~~~~~~

Subtask #1
56.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94328 KB Output is correct
2 Correct 55 ms 94328 KB Output is correct
3 Correct 57 ms 94328 KB Output is correct
4 Incorrect 344 ms 161528 KB Output isn't correct
5 Correct 92 ms 97528 KB Output is correct
6 Incorrect 82 ms 127488 KB Output isn't correct
7 Incorrect 80 ms 127348 KB Output isn't correct
8 Incorrect 78 ms 127276 KB Output isn't correct
9 Incorrect 132 ms 131756 KB Output isn't correct
10 Incorrect 79 ms 127188 KB Output isn't correct