oj.uz

답안 #55628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55628 2018-07-08T09:05:01 Z polyfish Rima (COCI17_rima) C++14
42 / 140
 1000 ms 63872 KB 
//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

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