Submission #55630

#TimeUsernameProblemLanguageResultExecution timeMemory
55630polyfishRima (COCI17_rima)C++14
42 / 140
1072 ms61008 KiB
//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 = 1101101017; 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] * 30 + s[p[i]][j] - 'a' + 1) % MOD; H1[i] = (H0[i] * 30 + 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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...