# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
24211 | 2017-06-01T16:15:26 Z | gs14004 | Rima (COCI17_rima) | C++11 | 843 ms | 214988 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<string, 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()][s[i]] = i; } for(int i=1; i<=n; i++){ succ[i] = hsh[s[i].size() - 1][s[i].substr(0, s[i].size() - 1)]; dp[i] = lh[i] + dp[succ[i]]; ans = max(ans, dp[i]); } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 167072 KB | Output is correct |
2 | Correct | 46 ms | 167072 KB | Output is correct |
3 | Correct | 39 ms | 167072 KB | Output is correct |
4 | Incorrect | 843 ms | 214988 KB | Output isn't correct |
5 | Correct | 69 ms | 173012 KB | Output is correct |
6 | Incorrect | 43 ms | 168904 KB | Output isn't correct |
7 | Incorrect | 49 ms | 168632 KB | Output isn't correct |
8 | Incorrect | 49 ms | 168420 KB | Output isn't correct |
9 | Incorrect | 129 ms | 175116 KB | Output isn't correct |
10 | Incorrect | 33 ms | 168448 KB | Output isn't correct |