Submission #24210

#	Time	Username	Problem	Language	Result	Execution time	Memory
24210		gs14004	Rima (COCI17_rima)	C++11	56 / 140	739 ms	205484 KiB

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 (stderr)

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 / 140