Submission #24210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24210	2017-06-01T16:14:24 Z	gs14004	Rima (COCI17_rima)	C++11	56 / 140	739 ms	205484 KB

rima

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 409;
const int mod2 = 1e9 + 433;
typedef pair<int, int> pi;

lint get_hash(string &s, int st, int ed){
	lint h1 = 0;
	lint h2 = 0;
	for(int i=st; i<ed; i++){
		h1 = h1 * 257 + s[i];
		h2 = h2 * 257 + s[i];
		h1 %= mod1;
		h2 %= mod2;
	}
	return h1 * mod2 + h2;
}

int n, lh[500005], succ[500005], dp[500005];
string s[500005];
char buf[3000005];
map<lint, int> hsh[3000005];

int lcp(string &a, string &b){
	for(int i=0; i<a.size(); i++){
		if(a[i] != b[i]) return i;
	}
	return a.size();
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%s", buf);
		s[i] = buf;
		reverse(s[i].begin(), s[i].end());
	}
	sort(s+1, s+n+1, [&](const string &a, const string &b){
		return make_pair(a.size(), a) < make_pair(b.size(), b);
	});
	for(int i=1; i<=n; ){
		int e = i;
		while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
		for(int j=i; j<e; j++){
			lh[j] = e - i;
		}
		i = e;
	}
	int ans = 0;
	for(int i=1; i<=n; i++){
		hsh[s[i].size()][get_hash(s[i], 0, s[i].size())] = i;
	}
	for(int i=1; i<=n; i++){
		lint p = get_hash(s[i], 0, s[i].size() - 1);
		succ[i] = hsh[s[i].size() - 1][p];
		dp[i] = lh[i] + dp[succ[i]];
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

Compilation message

rima.cpp: In function 'int lcp(std::__cxx11::string&, std::__cxx11::string&)':
rima.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++){
                ^
rima.cpp: In function 'int main()':
rima.cpp:46:65: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e <= n && s[e].size() == s[i].size() && lcp(s[i], s[e]) >= s[i].size() - 1) e++;
                                                                 ^
rima.cpp:35:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
rima.cpp:37:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
                   ^

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	167072 KB	Output is correct
2	Correct	39 ms	167072 KB	Output is correct
3	Correct	29 ms	167072 KB	Output is correct
4	Incorrect	739 ms	205484 KB	Output isn't correct
5	Correct	99 ms	170108 KB	Output is correct
6	Incorrect	59 ms	168092 KB	Output isn't correct
7	Incorrect	53 ms	167972 KB	Output isn't correct
8	Incorrect	46 ms	167888 KB	Output isn't correct
9	Incorrect	166 ms	171276 KB	Output isn't correct
10	Incorrect	63 ms	167904 KB	Output isn't correct