oj.uz

답안 #24210

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24210 2017-06-01T16:14:24 Z gs14004 Rima (COCI17_rima) C++11
56 / 140
 739 ms 205484 KB 
#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

# 결과 실행 시간 메모리 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