Submission #55628

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55628	2018-07-08T09:05:01 Z	polyfish	Rima (COCI17_rima)	C++14	42 / 140	1000 ms	63872 KB

rima

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 500002;
const int MOD = 1000000007;

int n, p[MAX_N];
int64_t H0[MAX_N], H1[MAX_N];
string s[MAX_N];

bool cmp(int a, int b) {
	return s[a].size()>s[b].size();
}

void enter() {
	cin >> n;
	for (int i=1; i<=n; ++i)
		cin >> s[i];
}

void init() {
	for (int i=1; i<=n; ++i)
		p[i] = i;
	sort(p+1, p+n+1, cmp);
	for (int i=1; i<=n; ++i) {
		for (int j=(int)s[p[i]].size()-1; j>0; --j)
			H0[i] = (H0[i] * 27 + s[p[i]][j] - 'a' + 1) % MOD;
		H1[i] = (H0[i] * 27 + s[p[i]][0] - 'a' + 1) % MOD;
	}
}

void solve() {
	map<int64_t, int> mp;
	int res = 0;
	for (int i=1; i<=n; ++i) {
		int tmp = max(mp[H0[i]], mp[H1[i]]) + 1;
		res = max(res, tmp);
		mp[H0[i]] = max(mp[H0[i]], tmp);
		mp[H1[i]] = max(mp[H1[i]], tmp);
	}
	cout << res;
}

int main() {
	//#define OFFLINE_JUDGE doraemon
	#ifdef OFFLINE_JUDGE
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	enter();
	init();
	solve();
}

Subtask #1

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	15992 KB	Output is correct
2	Correct	20 ms	16104 KB	Output is correct
3	Incorrect	17 ms	16144 KB	Output isn't correct
4	Execution timed out	1084 ms	63872 KB	Time limit exceeded
5	Correct	50 ms	63872 KB	Output is correct
6	Incorrect	27 ms	63872 KB	Output isn't correct
7	Incorrect	24 ms	63872 KB	Output isn't correct
8	Incorrect	22 ms	63872 KB	Output isn't correct
9	Incorrect	69 ms	63872 KB	Output isn't correct
10	Incorrect	22 ms	63872 KB	Output isn't correct