Submission #26635

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26635	2017-07-03T14:49:50 Z	gs14004	Rima (COCI17_rima)	C++14	140 / 140	786 ms	225424 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, vtx[500005], par[500005], cst[500005];
string s[500005];
char buf[3000005];
map<lint, int> hsh[3000005];
vector<int> gph[500005];

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

bool vis[500005];
int dp[500005], check[500005];

pi dfs(int x, int p){
	vis[x] = 1;
	pi ret(0, x);
	for(auto &i : gph[x]){
		if(i != p){
			ret = max(ret, dfs(i, x));
		}
	}
	ret.first += cst[x];
	return ret;
}

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; i++){
		hsh[s[i].size()][get_hash(s[i], 0, s[i].size())] = i;
	}
	for(int i=1; i<=n; ){
		int p = hsh[s[i].size() - 1][get_hash(s[i], 0, s[i].size() - 1)];
		if(p > 0){
			gph[vtx[p]].push_back(i);
			gph[i].push_back(vtx[p]);
			check[i] = 1;
		}
		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++){
			vtx[j] = i;
			cst[j] = e - i;
		}
		i = e;
	}
	int ans = 0;
	for(int i=n; i; i--){
		if(vtx[i] != i) continue;
		vector<int> v;
		for(auto &j : gph[i]){
			v.push_back(dp[j]);
		}
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		if(v.size() >= 2) ans = max(ans, v[0] + v[1] + check[i] + cst[i]);
		if(v.size() >= 1) ans = max(ans, v[0] + check[i] + cst[i]);
		dp[i] = (v.size() ? v[0] : 0) + cst[i];
	}
	cout << ans << endl;
}

Compilation message

rima.cpp: In function 'int lcp(std::__cxx11::string&, std::__cxx11::string&)':
rima.cpp:29: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:71: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:51:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
rima.cpp:53:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
                   ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	183184 KB	Output is correct
2	Correct	43 ms	183184 KB	Output is correct
3	Correct	66 ms	183184 KB	Output is correct
4	Correct	786 ms	225424 KB	Output is correct
5	Correct	119 ms	186220 KB	Output is correct
6	Correct	59 ms	184204 KB	Output is correct
7	Correct	73 ms	184084 KB	Output is correct
8	Correct	63 ms	184000 KB	Output is correct
9	Correct	203 ms	187520 KB	Output is correct
10	Correct	63 ms	184016 KB	Output is correct