Submission #24851

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24851	2017-06-15T21:01:27 Z	gs14004	Rima (COCI17_rima)	C++11	70 / 140	823 ms	226796 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];

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; ){
		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=1; i<=n; i++){
		hsh[s[i].size()][get_hash(s[i], 0, s[i].size())] = i;
	}
	set<pi> st;
	for(int i=1; i<=n; i++){
		lint p = get_hash(s[i], 0, s[i].size() - 1);
		par[i] = hsh[s[i].size() - 1][p];
		if(par[i]){
			int s = vtx[par[i]];
			int e = vtx[i];
			if(st.find(pi(s, e)) != st.end()) continue;
			st.insert(pi(s, e));
			gph[s].push_back(e);
			gph[e].push_back(s);
		}
	}
	int ret = 0;
	for(int i=1; i<=n; i++){
		if(!vis[i]){
			ret = max(ret, dfs(dfs(i, -1).second, -1).first);
		}
	}
	cout << ret << 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:61: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:68:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = 0;
      ^
rima.cpp:50:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
rima.cpp:52:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf);
                   ^

Subtask #1

70.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	179276 KB	Output is correct
2	Correct	46 ms	179276 KB	Output is correct
3	Correct	43 ms	179276 KB	Output is correct
4	Correct	823 ms	226796 KB	Output is correct
5	Correct	103 ms	182444 KB	Output is correct
6	Incorrect	66 ms	180296 KB	Output isn't correct
7	Incorrect	46 ms	180176 KB	Output isn't correct
8	Incorrect	56 ms	180092 KB	Output isn't correct
9	Incorrect	173 ms	183744 KB	Output isn't correct
10	Incorrect	59 ms	180108 KB	Output isn't correct